bzoj P4870: [Shoi2017]组合数问题—

题意：求解——

$$(C^{r}_{nk}+C^{r+k}_{nk}+C^{r+2k}_{nk}+...+C^{r+(n-1)k}_{nk}+...)mod(P)$$

其中$C^{m}_{n}$表示从n中选m个的方案数

保证$1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^{30} − 1$

http://www.lydsy.com/JudgeOnline/problem.php?id=4870

一看r，k很小就很自然地想到矩阵快速幂；

然后枚举nk

一开始打算横着递推，处理出每个C，同时处理C的部分和，然而横着递推有问题；

最后发现竖着递推，直接处理C的部分和非常方便。

S(x,y)表示C(ik+x,y)的和，可以从S((x-1+k)%k，y-1)+S(x,y-1)得出；

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

LL P,N,K,R;

struct Matrix{

    LL _[][];

};

Matrix operator * (Matrix a,Matrix b){

    Matrix c;

    int i,j,k;

    memset(c._,,sizeof(c._));

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

        for(k=;k<;k++)

            if(a._[i][k])

                for(j=;j<;j++)

                    if(b._[k][j])

                        (c._[i][j]+=(a._[i][k]*b._[k][j])%P)%=P;

    return c;

}

Matrix x,ret;

void Sqr(LL );

int main()

{

    int i;

    scanf("%lld%lld%lld%lld",&N,&P,&K,&R);

    for(i=;i<K;i++)

        x._[(i-+K)%K][i]++,x._[i][i]++;

    Sqr(N*K);

    printf("%lld\n",ret._[][R]);

    return ;

}

void Sqr(LL n){

    int i;

    for(i=;i<;i++)ret._[i][i]=;

    while(n){

        if(n&)

            ret=ret*x;

        n>>=,x=x*x;

    }

}

存在的问题：
见到组合数就认为不可能在合理的时间内完成行间递推

巴特西

bzoj P4870: [Shoi2017]组合数问题——solution

最新文章

热门文章