洛谷·[SHOI2015]超能粒子炮·改

超能粒子炮·改"/>

洛谷·[SHOI2015]超能粒子炮·改

初见安~这里是传送门：洛谷P4345 [SHOI2015]超能粒子炮·改

题解

推推式子就好。显然要求的是这个：

然后你会了。

好了说人话。题意求这个，没问题吧

考虑优化。数学方法应该拆不开了，所以看到组合数用Lucas定理拆开：

可以发现n%p是定值，而i%p又只有p种情况。所以考虑枚举i%p的值以及这个值的出现次数，也就是后面对应的整除情况出现的次数：

可以发现后面一个sum显然就是我们所求问题的子问题，所以递归求解即可。这样的话复杂度是，显然跑不过。

尝试把两个sum分开，后面的上界显然只有当时为，否则为。换言之只有两种情况。

所以再分开这两种情况为：

显然两部分的前半部分的sum都相当于求C的前缀和，可以预处理优化掉，后半部分递归求解即可。

复杂度大概是，可以过。

上代码——

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define maxn 3005
using namespace std;
typedef long long ll;
const ll mod = 2333;
ll read() {ll x = 0, f = 1, ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();return x * f;
}int T;
ll n, k, C[maxn][maxn], S[maxn][maxn];
ll Lucas(ll n, ll k) {if(n < k || k < 0) return 0;//边界情况if(!k) return 1; ll ans = 0;ans = S[n % mod][k % mod] * Lucas(n / mod, k / mod) % mod;//前一个sumif(min(k, mod - 1) > k % mod) //稍微特判一下避免撞边界，下面前缀和差分ans = (ans + (S[n % mod][min(k, mod - 1)] - S[n % mod][k % mod] + mod) * Lucas(n / mod, k / mod - 1) % mod) % mod;return ans;
}signed main() {for(int i = 0; i < mod; i++) {//预处理，C是组合数S，是前缀和C[i][0] = S[i][0] = 1;for(int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod, S[i][j] = (S[i][j - 1] + C[i][j]) % mod;//因为前缀和可能会超出n%p，所以多处理些for(int j = i + 1; j < mod; j++) S[i][j] = S[i][j - 1];}T = read();while(T--) {n = read(), k = read(); if(k > n) k = n;printf("%lld\n", Lucas(n, k));}return 0;
}

迎评：）
——End——