题解 P3746 【[六省联考2017]组合数问题】

UltiMadow · 2020-01-21 23:05:24 · 题解

过的第350道题，写个题解庆祝一下

前言

翻了翻题解发现全部都是矩阵乘法，复杂度都是 O(k^3logn)，于是我来补一篇复杂度 O(k^2logn) 的做法

不过在看这篇题解前，请尽量先理解矩阵乘法的做法，因为我就不再细说矩阵乘法的做法了

解法

我们先来康康矩阵乘法的递推式：

其中 0\le l<k

我们发现，既然我们可以从第 i-1 个状态转移，那么我们是不是可以考虑把两个状态合并呢？

于是，我们推出了下面的式子：

其中对于任意的 i_1+i_2=i 都可以通过上面的表达式由 i_1 和 i_2 推出 i

那么，如何选择 i_1 和 i_2 就成了本题的一个关键的问题

我们发现，当 i 为偶数时，我们可以选 i_1=i_2=\frac{i}{2} 时我们只需要通过一组 f[i_1] 的数据就可以得到 f[i] 了，这样就可以大大减少本题的计算量

接下来我们就可以采用快速幂的方法来进行转移了（具体在代码里说明）

代码

#include<bits/stdc++.h>
#define int long long//其实本题可以不用long long
using namespace std;
int n,k,r,p;
int c[110][110];
struct Node
{
    int a[110];
}f;
Node operator * (Node x,Node y)
{
    Node ret;
    for(int i=0;i<100;i++)ret.a[i]=0;
    for(int i=0;i<k;i++)
        for(int j=0;j<k;j++)
            ret.a[i]=(ret.a[i]+x.a[j]*y.a[(i-j+k)%k])%p;
    return ret;
}
Node qpow(Node x,int y)//快速幂
{
    Node ret=x;//初始我们传入的x是f[1]的情况
    while(y)//这里，我们把每一次乘法看成一次转移，y就是转移次数
    {
        if(y%2==1)ret=ret*x;
        x=x*x;y>>=1;
    }
    return ret;
}
signed main()
{
    scanf("%lld%lld%lld%lld",&n,&p,&k,&r);
    c[1][1]=1;
    for(int i=2;i<=k+1;i++)
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
    for(int i=0;i<k;i++)
        f.a[i]=c[k+1][i+1];//f[1][i]就是C(k,i)的组合数
    f.a[0]++;
    printf("%lld",qpow(f,n-1).a[r]%p);
    return 0;
}