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

· · 题解

大家的题解真的是太巨佬了,好多东西都没有讲啊...想我这种巨弱是根本看不懂啊.
搞了一两个小时终于搞出来了,我来发一下我的想法.

预备知识:

组合数递推公式.

矩阵乘法运算法则.

矩阵乘法运算无交换律.

矩阵乘法优化递推.

基本数学推导能力.

题目分析:

由一般式子转化为题目上的式子

由取模的常识,我们知道后面那个 modp 就每次运算都 mod 一下就好了.

这个↓公式大家都知道吧

那么

这个也对吧.

思考题目上的式子的意义

化成题目上说的n,m

n=n X k 前面的n是指上面那个式子的n,后面那个n就是题目上输入的那个n.

m=i X k + r

所以整个式子带进去输入的数据就是

我们设F[i,j]

这样我们能得到递推式

但是还有个问题:

j-1<0即j=0了怎么办?

回归它的定义,j-1小于0了,那就是相当于a减了1,然后取到最后一位a*k+k-1

所以我们还有一个特殊的式子

最前面那个是F[i,0].

那么总的递推公式就出来了

前面是F[i,j]

构造矩阵:

首先我们不考虑i那一层的话,自然就是k X k的转移矩阵(0~k-1行/列)和1 X k(k X 1也行了,我这里是1 X k)的初始矩阵

我们发现它是相当于原来的矩阵依次向下换一格,然后把最后一个放到最上面,与原矩阵相加的结果.

最后是F[k,k]

我们如果想要实现依次向下换一格,然后把最后一个放到最上面大家都知道.

用一个在对角线左下一格全是1的矩阵乘一下就好了.

不过还要注意最后一行在最上面有个1,把最下面的那个换上来

转移矩阵构造方法(建议复制下来自己运行一下):

memset(val,0,sizeof(val));
for(int i=0;i<k-1;++i)
    val[i+1][i]=1;
val[1][k]=1;

至于如何把原来矩阵复制一遍,就是乘上一个1矩阵啊.

memset(val,0,sizeof(val));
for(int i=0;i<k;++i)
    val[i][i]=1;

那么由于矩阵可以加,满足分配律

A × C + B × C = ( A + B ) × C

自然我们上面的操作就可以合并了.

生成一个这样的矩阵就是最终的转移矩阵了

memset(val,0,sizeof(val));
for(int i=0;i<k;++i){
    val[i][i]=1;
    val[(i+1)%k][i]=1;
}

初始矩阵

C0,0=1

那么初始矩阵的生成方法

memset(val,0,sizeof(val));
val[0][0]=1;

观察这个矩阵的性质,乘一次就相当于取一列,所以我们干脆不乘了,直接取第一列.

答案就是转移矩阵的r行0列.

这个题乘出来的矩阵好像是对称的...不知道为什么还是我水过去的.

激动人心的对拍代码

#include<bits/stdc++.h>
using namespace std;
long long n,P,k,r;
struct matrix{
    long long val[51][51];
    void to_one(){for(int i=0;i<50;++i)val[i][i]=1;}
    matrix operator*(const matrix &a)const{
        matrix c;
        for(int i=0;i<k;++i)
        for(int j=0;j<k;++j){
            c.val[i][j]=0;
            for(int p=0;p<k;++p)
            c.val[i][j]=(c.val[i][j]+val[i][p]*a.val[p][j])%P;
        }
        return c;
    }
    void Debug(){//有趣的Debug
        for(int i=0;i<k;++i)for(int j=0;j<k;++j)
            cout<<val[i][j]<<(j==k-1?"\n":" ");
    }
}ans,opt;
int main(){
    scanf("%lld%lld%lld%lld",&n,&P,&k,&r);
    for(int i=0;i<k;++i){
        opt.val[i][i]=1;
        opt.val[(i+1)%k][i]=1;
    }
    ans.to_one(); 
    n=n*k;
    for(;n;n>>=1,opt=opt*opt)
        if(n&1) ans=opt*ans;
    cout<<ans.val[r][0];
    return 0;
}