http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=34985? ? ? ?

題意：給你0~k個數(shù)組合長度為n的字符串有多少種，這長度為n的字符串的子序列不能存在0~k的全排列。

題解：參考Kefault大牛博客：http://blog.csdn.net/knight_kaka/article/details/38616039? ??

因為n很大，所以很容易想到要使用矩陣快速冪來加速。?

那么接下來就是推導公式了。?

我們定義dp[i][j]為長度為i，尾部j個字母均不相同的字符串的數(shù)目。?

那么我們很容易推出dp[i][j]的遞推公式了:?

dp[i][j]=dp[i-1][j-1]*(k-j+2)+dp[i-1][j]+……+dp[i-1][k];?

這是什么意思呢？?

首先我們知道，dp[i]和dp[i-1]只差一個字母，假設我們在dp[i-1]后面加上一個字母，這個?

字母可以是和dp[i-1]尾部幾個不同的字母中的一個相同，也可以不同（例：假如dp[i-1]=……0123,?

k=7,這是我們?yōu)榱藰嫵蒬p[i],我們可以在尾部加上4、5、6、7，或者0、1、2、3）?

大家會發(fā)現(xiàn)如果是4、5、6、7，那么dp[i-1][j-1]就變成了dp[i][j](看定義),?

如果是0、1、2、3，那么dp[i-1][j-1]就會相應變成dp[i][j],dp[i][j-1],dp[i][j-2],dp[i][j-3],?

綜上我們?yōu)榱藰嫵蒬p[i][j],就可以使用dp[i-1][j-1]---dp[i-1][k]來構造。?

然后剩下的事就是構造矩陣了，很簡單，不贅述。?

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long LL; #define mod 20140518 int 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;} }

總結

以上是生活随笔為你收集整理的bnu- 34985 Elegant String的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。