[SHOI2015]超能粒子炮·改

超能粒子炮·改"/>

[SHOI2015]超能粒子炮·改

SHOI2015

一句话题意：

~~~~~~       多组数据，给定 n , k n,k n,k , , ,求 ∑ i = 0 k C n i % 2333 ， n , k &lt; = 1 0 9 \sum_{i=0}^kC_n^i\%2333，n,k&lt;=10^9 ∑i=0k​Cni​%2333，n,k<=109。

• n , k n,k n,k都很大，考虑Lucas定理。但是 k k k仍然很大，暴力枚举显然不现实。拆式子吧。
• 设 f ( n , k ) = ∑ i = 0 k C n i % p f(n,k)=\sum_{i=0}^kC_n^i\%p f(n,k)=∑i=0k​Cni​%p，则：
  f ( n , k ) = ∑ i = 0 k C n % p i % p ⋅ C n / p i / p f(n,k)=\sum_{i=0}^kC_{n\%p}^{i\%p}·C_{n/p}^{i/p} f(n,k)=i=0∑k​Cn%pi%p​⋅Cn/pi/p​
  = { C n % p 0 C n / p 0 + C n % p 1 C n / p 0 + … C n % p p − 1 C n / p 0 C n % p 0 C n / p 1 + C n % p 1 C n / p 1 + … C n % p p − 1 C n / p 1 … … C n % p 0 C n / p k / p − 1 + C n % p 1 C n / p k / p − 1 + … C n % p p − 1 C n / p k / p − 1 + C n % p 0 C n % p k / p … C n % p k % p C n / p k / p =\begin{cases} C_{n\%p}^0C_{n/p}^0+C_{n\%p}^1C_{n/p}^0+…C_{n\%p}^{p-1}C_{n/p}^0\\ C_{n\%p}^0C_{n/p}^1+C_{n\%p}^1C_{n/p}^1+…C_{n\%p}^{p-1}C_{n/p}^1\\ ……\\ C_{n\%p}^0C_{n/p}^{k/p-1}+C_{n\%p}^1C_{n/p}^{k/p-1}+…C_{n\%p}^{p-1}C_{n/p}^{k/p-1}\\ \end{cases}+C_{n\%p}^{0}C_{n\%p}^{k/p}…C_{n\%p}^{k\%p}C_{n/p}^{k/p} =⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​Cn%p0​Cn/p0​+Cn%p1​Cn/p0​+…Cn%pp−1​Cn/p0​Cn%p0​Cn/p1​+Cn%p1​Cn/p1​+…Cn%pp−1​Cn/p1​……Cn%p0​Cn/pk/p−1​+Cn%p1​Cn/pk/p−1​+…Cn%pp−1​Cn/pk/p−1​​+Cn%p0​Cn%pk/p​…Cn%pk%p​Cn/pk/p​
  = f ( n % p , p − 1 ) ∗ f ( n / p , k / p − 1 ) + f ( n % p , k % p ) ∗ C n / p k / p =f(n\%p,p-1)*f(n/p,k/p-1)+f(n\%p,k\%p)*C_{n/p}^{k/p} =f(n%p,p−1)∗f(n/p,k/p−1)+f(n%p,k%p)∗Cn/pk/p​
• 前面的两个 f f f相乘是做了一个类似整除分块的东西，然后提项化简得到的。对于 f ( n % p , p − 1 ) f(n\%p,p-1) f(n%p,p−1)和 f ( n % p , k % p ) f(n\%p,k\%p) f(n%p,k%p)可以预处理出来，至于 f ( n / p , k / p − 1 ) f(n/p,k/p-1) f(n/p,k/p−1)和 C n / p k / p C_{n/p}^{k/p} Cn/pk/p​使用递归和Lucas分别求解。
• 注意点：C在本题中使用杨辉三角预处理，查询 O ( 1 ) O(1) O(1)，如果用费马小定理求，多乘了一个 l o g log log，会T掉两组。
• O ( n ) O(n) O(n)预处理，O(1)查询组合数这种方法只适用于对 1 n 1~n 1 n的所有数都与 m o d mod mod存在逆元。所以本题不方便使用。

Coding

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=2333;
const int N=3010;
int t;ll n,k,f[N][N],c[N][N];
ll power(int a,int b){ll res=1;for(;b;b>>=1){if(b&1) res=res*a%mod;a=a*a%mod;}return res;
}
ll Luca(ll n,ll k){if(n<k) return 0;if(!n) return 1;return Luca(n/mod,k/mod)*c[n%mod][k%mod]%mod;
}
ll F(ll n,ll k){//if(k<0) return 0;//if(!n) return 1;
//	if(!k) return 1;if(n<=3000&&k<=3000) return f[n][k];ll c=Luca(n/mod,k/mod);return (f[n%mod][mod-1]*F(n/mod,k/mod-1)%mod+c*f[n%mod][k%mod])%mod;
}
int main(){scanf("%d",&t);c[0][0]=1;for(int i=1;i<=3000;++i) c[i][i]=c[i][0]=1;for(int i=1;i<=3000;++i) for(int j=1;j<=3000;++j) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;f[0][0]=1;for(int i=1;i<=3000;++i) f[i][0]=1;for(int i=0;i<=3000;++i){for(int j=1;j<=3000;++j){f[i][j]=(f[i][j-1]+c[i][j])%mod;}}while(t--){scanf("%lld%lld",&n,&k);printf("%lld\n",F(n,k));}return 0;
}