本文共 1714 字，大约阅读时间需要 5 分钟。

题意：给你0~k个数组合长度为n的字符串有多少种，这长度为n的字符串的子序列不能存在0~k的全排列。

题解：参考大牛博客：    

1. 因为n很大，所以很容易想到要使用矩阵快速幂来加速。 
2. 那么接下来就是推导公式了。 
3. 我们定义dp[i][j]为长度为i，尾部j个字母均不相同的字符串的数目。 
4. 那么我们很容易推出dp[i][j]的递推公式了: 
5. dp[i][j]=dp[i-1][j-1]*(k-j+2)+dp[i-1][j]+……+dp[i-1][k]; 
6. 这是什么意思呢？ 
7. 首先我们知道，dp[i]和dp[i-1]只差一个字母，假设我们在dp[i-1]后面加上一个字母，这个 
8. 字母可以是和dp[i-1]尾部几个不同的字母中的一个相同，也可以不同（例：假如dp[i-1]=……0123, 
9. k=7,这是我们为了构成dp[i],我们可以在尾部加上4、5、6、7，或者0、1、2、3） 
10. 大家会发现如果是4、5、6、7，那么dp[i-1][j-1]就变成了dp[i][j](看定义), 
11. 如果是0、1、2、3，那么dp[i-1][j-1]就会相应变成dp[i][j],dp[i][j-1],dp[i][j-2],dp[i][j-3], 
12. 综上我们为了构成dp[i][j],就可以使用dp[i-1][j-1]---dp[i-1][k]来构造。 
13. 然后剩下的事就是构造矩阵了，很简单，不赘述。 

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;typedef long long LL;#define mod 20140518int k;struct Z{    LL m[10][10];    Z(){memset(m,0,sizeof(m));}    void init(){//单位矩阵        for(int i = 0;i < k;i++)            m[i][i] = 1;    }    void Init(){//构造矩阵        for(int i = 0;i < k;i++)            for(int j = 0;j <=i ;j++)                m[i][j] = 1;        for(int i = 0;i < k-1;i++)            m[i][i+1] = k - i;    }};Z operator * (Z a, Z b){//矩阵乘法    Z c;    for(int i = 0;i < k;i++)        for(int r = 0;r < k;r++)            for(int j = 0;j < k;j++)                c.m[i][j] = (c.m[i][j] + a.m[i][r]*b.m[r][j]) % mod;    return c;}Z Pow(LL n){//快速幂    Z ret,s;    ret.init();s.Init();    while(n){        if(n&1) ret = ret * s;        s = s * s;        n >>= 1;    }    return ret;}int main(){    int t,ca = 1;    LL n;    cin >> t;    while(t--){        cin >> n >> k;        printf("Case #%d: ",ca++);        Z ret;        ret = Pow(n-1);        LL ans = 0;        for(int i = 0;i < k;i++)            ans = (ans + ret.m[0][i] * (k+1)) % mod;        cout << ans << endl;    }}
      
     
    
   

转载地址：http://ycsgi.baihongyu.com/