[BZOJ 4591] 超能粒子炮-改

Link:

Solution:

记录一下推$\sum_{i=0}^k C_n^i$的过程：

其实就是将相同的$i/p$合起来算，这样每个里面都是一个可以预处理的子问题

接下来递归下去算即可

Tip:推式子时尽量化出与模数相关的量方便预处理

Code:

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

#define pb push_back

typedef double db;

typedef long long ll;

typedef pair<int,int> P;

int T;const int MOD=;

ll C[MOD+][MOD+],sum[MOD+][MOD+];

ll Lucas(ll x,ll y)

{

    if(y==) return ;

    return Lucas(x/MOD,y/MOD)*C[x%MOD][y%MOD]%MOD;

}

ll cal(ll n,ll k)

{

    if (k<) return ;

    return (cal(n/MOD,k/MOD-)*sum[n%MOD][MOD-]+Lucas(n/MOD,k/MOD)*sum[n%MOD][k%MOD])%MOD;

}

int main()

{

    C[][]=;sum[][]=;

    for (int i=;i<MOD;i++) sum[][i]=;

    for (int i=;i<MOD;i++)

    {

        C[i][]=sum[i][]=;

        for (int j=;j<=i;j++) C[i][j]=(C[i-][j-]+C[i-][j])%MOD;

        for (int j=;j<MOD;j++) sum[i][j]=(sum[i][j-]+C[i][j])%MOD;

    }

    scanf("%d",&T);

    while (T--)

    {

        ll n,k;

        scanf("%lld%lld",&n,&k);

        printf("%lld\n",cal(n,k));

    }

    return ;

}

巴特西

[BZOJ 4591] 超能粒子炮-改

Link:

Solution:

Code:

最新文章

热门文章