[BZOJ4870][Shoi2017]组合数问题 dp+矩阵乘

2022-10-21 21:28:41

4870: [Shoi2017]组合数问题

Time Limit: 10 Sec Memory Limit: 512 MB

Description

Input

第一行有四个整数 n, p, k, r，所有整数含义见问题描述。

1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 − 1

Output

一行一个整数代表答案。

Sample Input

2 10007 2 0

Sample Output

题解：

今年的省选题……

题目的要求很简单，就是求满足要求的组合数在膜（？）意义下的和，但这其实是一道假的数学题。

不难发现，对于符合要求的C(n*k)^x中的x都有x%k==r

我们考虑组合数最原始的应用：在一堆物品里选一些物品出来，那么题目的含义就是在n*k个物品中选x个物品，使x%k=r，求方案数

这不就是个背包吗？

那么我们设dp数组f[i][j]为前i个物品选出一些物品，使得物品的个数x%k==j

那么不难写出转移方程：f[i][j]=f[i-1][j]+f[i-1][(j-1+k)%k]（前者表示不选第i个，后者表示选）

这显然是一个线性的递推式，因此我们考虑矩阵乘优化

设矩阵A中A[i][j]表示从%k=i转移到%k=j的方案数

那么我们的目标就是pow(A，n)之后的A[0][r];

初始化的时候，把所有的A[j][j]++,所有A[(j-1+k)%k][j]++（类比上面的转移方程）

然后再来一个单位矩阵一乘就好了。代码见下：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 typedef long long LL;

 const int N=;

 LL n,p,k,r;

 struct marx

 {

     LL m[N][N];

     inline void print()

     {

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

         {

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

                 printf("%lld ",m[i][j]);

             printf("\n");

         }

         printf("\n");

     }

     inline void clear(){memset(m,,sizeof(m));}

     marx operator * (const marx &b) const

     {

         marx c;c.clear();

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

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

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

                     c.m[i][j]=(c.m[i][j]+m[i][u]*b.m[u][j])%p;

         return c;

     }

 }A,B,C;

 int main()

 {

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

     A.clear(),B.clear(),C.clear();

     C.m[][]=;

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

         B.m[j][j]=,A.m[(j-+k)%k][j]++,A.m[j][j]++;

     LL tmp=n*k;

     while(tmp)

     {

         if(tmp&)B=B*A;

         tmp>>=;A=A*A;

     }

     C=C*B;

     printf("%lld\n",C.m[][r]);

 }