P4345 超能粒子炮·改 一个不一样的思路

· · 题解

思路：

\sum_{i=0}^kC_n^i \operatorname{mod} p =\sum_{i=0}^k( C_{n/p}^{i/p} \times C_{n\operatorname{mod}p}^{i\operatorname{mod}p}) =\sum_{i=0}^{k}(C_{n/p/p}^{i/p/p}\times C_{n/p\operatorname{mod}p}^{i/p\operatorname{mod}p}\times C_{n\operatorname{mod}p}^{i\operatorname{mod}p})

也就是 i 在 p 进制下的每一位与 n 在 p 进制下的每一位的组合的乘积。

因此，我们可以借用数位动态规划的思想，枚举最高位 j，满足 i 与 n 第 j 位之前的值都相等，第 j 位的值不相等，之后的值随意，并计算其状态下的 i 对答案的贡献。


#include <bits/stdc++.h>

using namespace std;

const int mod=2333;

long long n, k;
int a[20], cnt_a, b[20], f[20], cnt_b, c[mod+7][mod+7], sum[mod+7][mod+7];

long long read(){
    long long x=0; bool f=0; char c;
    while(!isdigit(c=getchar())) if(c=='-') f=1;
    do x=x*10+c-48; while(isdigit(c=getchar()));
    return f?-x:x;
}

void init(){
    for(int i=0; i<=mod; i++)
        for(int j=0; j<=i; j++)
            c[i][j]=(j==0||j==i?1:c[i-1][j]+c[i-1][j-1])%mod;
    for(int i=0; i<=mod; i++)
        for(int j=0; j<=mod; j++)
            sum[i][j]=(j==0?1:sum[i][j-1]+c[i][j])%mod;
}

void run(){
    n=read(), k=read(), k=min(k, n);
    for(cnt_a=0; n; n/=mod) a[++cnt_a]=n%mod;
    for(cnt_b=0; k; k/=mod) b[++cnt_b]=k%mod;
    f[0]=1;
    for(int i=1; i<=cnt_a; i++) f[i]=f[i-1]*sum[a[i]][mod-1]%mod;
    int ans=0, suf=1;
    for(int i=cnt_b; i>=1; suf=suf*c[a[i]][b[i]]%mod, i--) 
        if(b[i]) ans=(ans+suf*f[i-1]%mod*sum[a[i]][b[i]-1])%mod;
    printf("%d\n", (ans+suf)%mod);
}

signed main()
{
    init();
    for(int T=read(); T; T--) run();
    return 0;
}