P4345 [SHOI2015]超能粒子炮·改 lucas

超能粒子炮·改 lucas"/>

P4345 [SHOI2015]超能粒子炮·改 lucas

我来解释一下后一步咋来的，就是把Ci/p提出去，然后类似整数分块，每次往下分都会算一部分，预处理杨辉三角前缀和，我看的洛谷第二个题解。

题干：

题目描述曾经发明了脑洞治疗仪与超能粒子炮的发明家 SHTSC 又公开了他的新发明：超能粒子炮・改——一种可以发射威力更加强大的粒子流的神秘装置。超能粒子炮・改相比超能粒子炮，在威力上有了本质的提升。它有两个参数nnn,kkk，它会向每个编号为000到kkk（包含两端）的位置iii发射威力为Cnimod2333C_{n}^{i} mod 2333Cni​mod2333的粒子流。现在 SHTSC 给出了他的超能粒子炮・改的参数，让你求出其发射的粒子流的威力之和除以233323332333所得的余数。
输入输出格式
输入格式：第一行一个整数 ttt表示数据组数。 之后 ttt 行，每行两个整数 nnn、kkk，含义如题面描述。输出格式：ttt 行，每行一个整数，表示其粒子流的威力之和模 233323332333 的值。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define duke(i,a,n) for(register int i = a;i <= n;++i)
#define lv(i,a,n) for(register int i = a;i >= n;--i)
#define clean(a) memset(a,0,sizeof(a))
const int INF = 1 << 30;
typedef long long ll;
typedef double db;
template <class T>
void read(T &x)
{char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-') op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op) x = -x;
}
template <class T>
void write(T x)
{if(x < 0) putchar('-'), x = -x;if(x >= 10) write(x / 10);putchar('0' + x % 10);
}
const int N = 2450;
const int mod = 2333;
ll t,n,k,c[N][N],f[N][N];
ll lucas(ll n,ll m)
{if(!m) return 1;if(n == m) return 1;if(n < m) return 0;return c[n % mod][m % mod] * lucas(n / mod,m / mod) % mod;
}
ll F(ll n,ll k)
{if(k < 0) return 0;if(!n) return 1;if(!k) return 1;if(n < mod && k < mod) return f[n][k];return (F(n / mod,k / mod - 1) * f[n % mod][mod - 1] % mod + lucas(n / mod,k / mod) * f[n % mod][k % mod]) % mod;
}
int main()
{read(t);c[0][0] = 1;duke(i,1,2350){c[i][0] = c[i][i] = 1;duke(j,1,i - 1){c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;}}f[0][0] = 1;duke(i,0,2350){f[i][0] = 1;}duke(i,0,2350){duke(j,1,2350){f[i][j] = (f[i][j - 1] + c[i][j]) % mod;}}while(t--){read(n);read(k);printf("%lld\n",F(n,k));}return 0;
}

转载于:.html