P3746 六省联考 2017 组合数问题

出题人: ZHX
出的很不错，调了一周才调出来。

六省联考 2017 组合数问题

题目描述

组合数 $C_n^m$ 表示的是从 $n$ 个互不相同的物品中选出 $m$ 个物品的方案数。举个例子， 从 $(1, 2, 3)$ 三个物品中选择两个物品可以有 $(1, 2)$，$(1, 3)$，$(2, 3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $C_n^m$ 的一般公式：

$C_n^m = \frac {n!} {m! \ (n - m)!}$

其中 $n! = 1 \times 2 \times \cdots \times n$。（特别地，当 $n = 0$ 时，$n! = 1$；当 $m > n$ 时，$C_n^m = 0$。）

小葱在 NOIP 的时候学习了 $C_i^j$ 和 $k$ 的倍数关系，现在他想更进一步，研究更多关于组合数的性质。小葱发现，$C_i^j$ 是否是 $k$ 的倍数，取决于 $C_i^j \bmod k$ 是否等于 $0$，这个神奇的性质引发了小葱对 $\mathrm{mod}$ 运算（取余数运算）的兴趣。现在小葱选择了是四个整数 $n, p, k, r$，他希望知道

$\left( \sum_{i = 0}^\infty C_{nk}^{ik + r} \right) \bmod p,$

即

$\left( C_{nk}^{r} + C_{nk}^{k + r} + C_{nk}^{2k + r} + \cdots + C_{nk}^{(n - 1)k + r} + C_{nk}^{nk + r} + \cdots \right) \bmod p$

的值。

输入格式

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

输出格式

一行一个整数代表答案。

样例 #1

样例输入 #1

2 10007 2 0

样例输出 #1

8

样例 #2

样例输入 #2

20 10007 20 0

样例输出 #2

176

提示

对于 $30\%$ 的测试点，$1 \leq n, k \leq 30$，$p$ 是质数；
对于另外 $5\%$ 的测试点，$p = 2$；
对于另外 $5\%$ 的测试点，$k = 1$；
对于另外 $10\%$ 的测试点，$k = 2$；
对于另外 $15\%$ 的测试点，$1 \leq n \leq 10^3, 1 \leq k \leq 50$，$p$ 是质数；
对于另外 $15\%$ 的测试点，$1 \leq n \times k \leq 10^6$，$p$ 是质数；
对于另外 $10\%$ 的测试点，$1 \leq n \leq 10^9, 1 \leq k \leq 50$，$p$ 是质数；
对于 $100\%$ 的测试点，$1 \leq n \leq 10^9, 0 \leq r < k \leq 50, 2 \leq p \leq 2^{30} - 1$。

推导

$\left( \sum_{i = 0}^\infty C_{nk}^{ik + r} \right) \bmod p$

对于这么个式子，不化简肯定是没法做的废话

下面进行一个简单的处理

设$\left( \sum_{i = 0}^\infty C_{nk}^{ik + r} \right) \bmod p=f(n,r)$

对于这种求和变形问题，有以下四种解决思路，这里只用到了前三种:

• 增加枚举量
• 交换枚举顺序
• 分离无关变量
• 换元法

$k$是题目中给出的，我们不妨利用组合数的卷积给它展开$k$次

组合数的卷积:$C(n,m)=\sum^k\limits_{i=0}C(k,i)\cdot C(n-k,m-i)$

得到这个：

$C(nk,ik+r)=\sum^\infty_{i=0}\sum^k_{j=0}C(k,j)\times{C(nk-k,ik+r-j)}$

这样式子里就会有两个变量了

把和j有关的提到前面来

得到：

$\sum^k_{j=0}C(k,j)\times{\sum^{\infty}_{i=0}}{C((n-1)k,ik+r-j})$

那不就是这个东西嘛：

$\sum^k_{j=0}C(k,j)\times{f(n-1,r-j)}$

所以我们得到：

$f(n,r)=\sum^k_{j=0}f(n-1,r-j)\cdot{C(k,j)}$

这个样子有没有很眼熟

是不是很像矩阵乘法？

那我们把它“稍微”变一下

设：$D[r-j][r]=C(k,j)$

加一维，变为：

$f_n[1][r]=\sum^k_{j=0}f_{n-1}[1][r-j]\cdot{D[r-j][r]}$

这样就可以愉快地做矩阵乘法了

注意变量是从零开始枚举的，因此有两种解决方法：

• 把第$0$维移到第$1$维
• 把第$0$维移到第$k$维

代码

1.

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,r,p;
struct matrix{
    int n,m;
    int z[100][100];
    matrix()
    {
        n=m=0;
        memset(z,0,sizeof(z));
    }
};
matrix D;
matrix f;
matrix operator*(const matrix &a,const matrix &b)
{
    matrix c;
    c.n=a.n;
    c.m=b.m;
    for(int i=0;i<=a.n;i++)
        for(int k=0;k<=a.m;k++)
            for(int j=0;j<=b.m;j++)
            {
                c.z[i][j]+=(1ll*a.z[i][k]*b.z[k][j])%p;
                c.z[i][j]=c.z[i][j]%p;
            }
    return c;
}
matrix ksm(matrix x,int y)
{
    if(y==1) return x;
    matrix z=ksm(x,y/2);
    z=z*z;
    if(y%2==1) z=z*x;
    return z;
}
int c[100][100];
void pre()
{
    D.n=k,D.m=k,f.n=0,f.m=k;
    for(int i=0;i<=k;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
    }
    for(int r=0;r<k;r++)
        for(int j=0;j<=k;j++)
        {
            int x=(r-j+k)%k;
            if(x-j==k) x=k;
            D.z[x][r]+=c[k][j];
            D.z[x][r]%=p;
        }
}
signed main()
{
    scanf("%lld%lld%lld%lld",&n,&p,&k,&r);
    pre();
    f.z[0][0]=1;//
    matrix ans=f*ksm(D,n);
    printf("%lld",ans.z[0][r]);//
    return 0;
}

2.

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,r,p;
struct matrix{
    int n,m;
    int z[100][100];
    matrix()
    {
        n=m=0;
        memset(z,0,sizeof(z));
    }
};
matrix D;
matrix f;
matrix operator*(const matrix &a,const matrix &b)
{
    matrix c;
    c.n=a.n;
    c.m=b.m;
    for(int i=1;i<=a.n;i++)
        for(int k=1;k<=a.m;k++)
            for(int j=1;j<=b.m;j++)
            {
                c.z[i][j]+=(a.z[i][k]*b.z[k][j])%p;
                c.z[i][j]=c.z[i][j]%p;
            }
    return c;
}
matrix ksm(matrix x,int y)
{
    if(y==1) return x;
    matrix z=ksm(x,y/2);
    z=z*z;
    if(y%2==1) z=z*x;
    return z;
}
int c[100][100];
void pre()
{
    D.n=k,D.m=k,f.n=1,f.m=k;
    for(int i=0;i<55;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
    }
    for(int r=0;r<k;r++)
        for(int j=0;j<=k;j++)
        {
            int x=(r-j+k)%k;
            D.z[x==0?k:x][r==0?k:r]+=c[k][j];
            D.z[x==0?k:x][r==0?k:r]%=p;
        }
}
signed main()
{
    scanf("%lld%lld%lld%lld",&n,&p,&k,&r);
    pre();
    f.z[1][1]=1;//
    matrix ans=f*ksm(D,n);
    printf("%lld",ans.z[1][r+1]);//
    return 0;
}

预处理时注意到底应该枚举哪些变量，注意细节处理。

---