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

超能粒子炮·改"/>

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

首先要知道 L u c a s Lucas Lucas定理
C n m % p = C n / p m / p × C n % p m % p % p \large C_{n}^{m}\%p=C_{n/p}^{m/p}\times C_{n\%p}^{m\%p}\%p Cnm​%p=Cn/pm/p​×Cn%pm%p​%p
可以理解为把原来变成p进制数然后每位分别算后乘起来
具体证明可以去问Lucas本人自己找吧
然后对于这题，我我们要求的是 ∑ i = 0 k C n i % p \large \sum\limits_{i=0}^{k}C_{n}^i\%p i=0∑k​Cni​%p
设 f ( n , k ) = 上 面 那 坨 f(n,k)=上面那坨 f(n,k)=上面那坨
f ( n , k ) = ∑ i = 0 k C n / p i / p × C n % p i % p % p f(n,k)=\sum\limits_{i=0}^kC_{n/p}^{i/p}\times C_{n\%p}^{i\%p}\%p f(n,k)=i=0∑k​Cn/pi/p​×Cn%pi%p​%p
仔细想想，如果把最后那个散块单独处理的话这里是可以写成
( ∑ i = 0 p − 1 C n / p i ) × ( ∑ i = 0 k / p − 1 C n % p i ) \large (\sum\limits_{i=0}^{p-1}C_{n/p}^i)\times (\sum\limits_{i=0}^{k/p-1}C_{n\%p}^i) (i=0∑p−1​Cn/pi​)×(i=0∑k/p−1​Cn%pi​)
就是
f ( n / p , k / p − 1 ) × f ( n % p , p − 1 ) \large f(n/p,k/p-1)\times f(n\%p,p-1) f(n/p,k/p−1)×f(n%p,p−1)
乘上散块
f ( n % p , k % p ) f(n\%p,k\%p) f(n%p,k%p)
就是答案了
code:

#include<bits/stdc++.h>
#define mod 2333
#define ll long long
using namespace std;
int c[mod + 5][mod + 5], f[mod + 5][mod + 5];
ll lucas(ll n, ll m) {if(n < m) return 0;if(n == m || ! m) return 1;return 1ll * c[n % mod][m % mod] * lucas(n / mod, m / mod) % mod;
}
ll F(ll n, ll m) {if(m < 0) return 0;if(!n || !m) return 1;if(n <= mod && m <= mod) return f[n][m];return (1ll * f[n % mod][mod - 1] * F(n / mod, m / mod - 1) % mod + lucas(n / mod, m / mod) * F(n % mod, m % mod) % mod) % mod;
}
int main() {for(int i = 0; i <= mod; i ++) c[i][0] = 1;for(int i = 1; i <= mod; i ++)for(int j = 1; j <= i; j ++)c[i][j] = (c[i - 1][j] + c[i - 1][j -  1]) % mod;for(int i = 0; i <= mod; i ++) f[i][0] = 1;for(int i = 0; i <= mod; i ++)for(int j = 1; j <= mod; j ++)f[i][j] = (f[i][j - 1] + c[i][j]) % mod;int t;ll n, m;scanf("%d", &t);while(t --) {scanf("%lld%lld", &n, &m);printf("%lld\n", F(n, m));}return 0;
}