首页 > 代码库 > BNUOJ 34985 Elegant String 2014北京邀请赛E题 动态规划 矩阵快速幂

BNUOJ 34985 Elegant String 2014北京邀请赛E题 动态规划 矩阵快速幂

Elegant String

Time Limit: 1000msMemory Limit: 65536KB
64-bit integer IO format: %lld      Java class name: Main


We define a kind of strings as elegant string: among all the substrings of an elegant string, none of them is a permutation of "0, 1,…, k".
Let function(n, k) be the number of elegant strings of length n which only contains digits from 0 to k (inclusive). Please calculate function(n, k).
 

Input

Input starts with an integer T (T ≤ 400), denoting the number of test cases.
 
Each case contains two integers, n and k. n (1 ≤ n ≤ 1018) represents the length of the strings, and k (1 ≤ k ≤ 9) represents the biggest digit in the string.
 

Output

For each case, first output the case number as "Case #x: ", and x is the case number. Then output function(n, k) mod 20140518 in this case. 
 

Sample Input

2
1 1
7 6

Sample Output

Case #1: 2
Case #2: 818503

Source

2014 ACM-ICPC Beijing Invitational Programming Contest

题解

在北京比赛的时候逗比的读错题了。。。题意是,一个长为n的字符串,只用了(0,1,2,...,k)这(k + 1)个数码。如果这个串的所有子串中,不出现一种(0, 1, 2, ..., k)的任意一个组合,那就称,这个串是优雅的。问所有长为n用了(k + 1)个数码的串中,有多少个优雅的串。

比如串(“112345678910”)就是一个优雅的串,但是串(“963852741023”)就不是一个优雅的串,因为后者有一个子串(“9638527410”)是一个排列。

正确思路是换方向思考!不要想着怎么去直接用容斥原理求,试着去构造一个串。

不妨先把n和k分别设为6和3。

假设这个串是个优雅串,那么这个串的所有长度为4( = k + 1)的子串一定不能出现(0, 1, 2, 3)的一个排列。

我这里假设我构造了一个子串(“023”),如果我希望这个串是个优雅串,那么就会有下一位必然不取"1"。因为一旦取"1",那么就有了一个排列了。。。

接着去想,假设子串是(“02”),那就有两种情况,第一种是接着从1和3中选一个构成一个长度为三的危险串。为什么是危险串呢?因为下一位必须不为1才能保证整个字符串是一个优雅串。当然还有第二种情况,那就是选0和2,这样相当于这个子串已经安全(近似安全)了。

所以就是规划问题了。

构造法

那么我们去想,假设k = 3吧。

对于第一位,我们可以从{0, 1, 2, 3}中随意选一个。不妨我们选取了0.

对于第二位,我们有两种选择,方案一,和前一位保持一致;方案二,和前一位不同。就不妨有S1("00"), S2("01");

对于第三位,对于S1,我们依然有两种选择:方案一,和前一位保持一致;方案二,和前一位不同。就不妨有S11("000"), S12("001");

对于S2.我们有三种选择:方案一,和前一位一致;方案二,和倒数第二位一致;方案三,和前两位不同。就不妨有S21("011"), S22("010"), S23("012");

S23违反了规则,所以他的子串都不是优雅的。舍弃。

对于第四位,S11,S21,都是两种方案:和前一位一致或不同;S12和S22都是有三种选择:方案一,和前一位一致;方案二,和倒数第二位一致;方案三,和前两位不同;类似的我们可以写出第五位第六位的情况。

这是在k = 3的时候。

我们把k推广出来,那就无非是这几种情况:

判断,从字符串末尾往前数k位所构成的子串中,有多少种字符。

如果是1种,那就有两个方案:A,和这些字符相同;B,和这些字符不同。

如果是2种,那就有三个方案:A,和这些字符中的第一种字符相同;B,和这些字符中的第二种字符相同;C,和这两个字符都不同。

如果是3种,那就有四个方案:A,和这些字符中的第一种字符相同;B,和这些字符中的第二种字符相同;C,和这些字符中的第三种字符相同;D,和这三个字符都不同。

以此类推。

如果是k - 1种,那就有k - 1个方案!为什么?因为根据规律,最后一个选项“和这些字符都不同”的结果就是导致这个串不是优雅串。所以就只剩下了k - 1个选项。

如果前面有了k种字符,嗯,直接舍弃。

dp[i][j]

所以设置dp[i][j],长度为i的一个字符串,满足从字符串末尾往前数,直到有j种字符为止的字串,并且总长度不超过k位的所构成的子串。

根据我们的构造思路,我们很快就能写出一些简单的等式。同样的以k = 3为例子,并且假设目前有一{其实就是所有满足长度为i的优雅串的集合}的串,不妨设i = 6。那么最后的一位(i = 6)的情况为:

dp[6][1] = dp[5][1] + 3 * dp[5][2]

1个dp[5][1]的意思是,直接和前一个数码一样。3个dp[5][2]的意思是,选取两个和前几个不同的数码,然后在选一个和最后一个相同的所以是3个。

dp[6][2] = dp[5][1] + dp[5][2] + 2 * dp[5][3]

1个dp[5][1]的意思是,直接和前一个数码一样。1个dp[5][2]的意思是,直接和前一个数码一样。2个dp[5][3]的意思是,选取1个和前几个不同的数码,然后在选一个和最后一个相同的所以是3个。

dp[6][3] = dp[5][1] + dp[5][2] + dp[5][3]

对于这个,直接选和前一个字符一样的就行。

转移方程如下:


所以就是矩阵快速幂的计算了。

既然都走到这步了,矩阵也就很好写了:


最后的结果就是


res就是答案了。

代码示例

/****	*@author    Shen	*@title     北京邀请赛E	*/#include <cstdio>#include <string>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef long long int64;const int MAXN = 11;const int MAXM = 11;const int Mod = 20140518;struct Matrax{    int n,m;    int64 mat[MAXN][MAXM];    Matrax():n(-1),m(-1){}    Matrax(int _n,int _m):n(_n),m(_m){        memset(mat,0,sizeof(mat));    }    void Unit(int _s){        n=_s; m=_s;        for (int i = 0; i < n; i++){            for (int j = 0; j < n; j++){                mat[i][j] = (i == j)? 1: 0;            }        }    }    void print(){        printf("n = %d, m =  %d\n", n, m);        for (int i = 0; i < n; i++){            for (int j = 0; j < m; j++)                printf("%8d", mat[i][j]);            printf("\n");        }    }};Matrax add_mod(const Matrax& a,const Matrax& b,const int64 mod){    Matrax ans(a.n,a.m);    for (int i = 0; i < a.n; i++){        for (int j = 0; j < a.m; j++){            ans.mat[i][j] = (a.mat[i][j] + b.mat[i][j]) % mod;        }    }    return ans;}Matrax mul(const Matrax& a,const Matrax& b){    Matrax ans(a.n, b.m);    for (int i = 0; i < a.n; i++){        for (int j = 0; j < b.m; j++){            int64 tmp = 0;            for (int k = 0; k < a.m; k++){                tmp += a.mat[i][k] * b.mat[k][j];            }            ans.mat[i][j] = tmp;        }    }    return ans;}Matrax mul_mod(const Matrax& a, const Matrax& b, const int mod){    Matrax ans(a.n, b.m);    for (int i = 0; i < a.n; i++){        for (int j = 0; j < b.m; j++){            int64 tmp = 0;            for (int k = 0; k < a.m; k++){                tmp += (a.mat[i][k] * b.mat[k][j]) % mod;            }            ans.mat[i][j] = tmp % mod;        }    }    return ans;}Matrax pow_mod(const Matrax& a, int64 k, const int mod){    Matrax p(a.n,a.m), ans(a.n,a.m);    p = a; ans.Unit(a.n);    if (k==0) return ans;    else if (k==1) return a;    else {        while (k){            if (k & 1){                ans=mul_mod(ans, p, mod);                k--;            }            else {                k /= 2;                p = mul_mod(p, p, mod);            }        }        return ans;    }}int64 n;int  k, t, tt;void solve(){    cin >> n >> k;    Matrax ans(k, 1);    //tmp = cef ^ (n - 1);    //ans = tmp * beg;    //res = ans.mat[0][0];    Matrax cef(k, k);    for (int i = 0; i < k; i++)        for (int j = 0; j <= i; j++)            cef.mat[i][j] = 1;    for (int i = 0; i < k - 1; i++)        cef.mat[i][i + 1] = k - i;    //cef.print();    Matrax beg(k, 1);    for (int i = 0; i < k; i++)        beg.mat[i][0] = k + 1;    Matrax tmp(k, k);    tmp = pow_mod(cef, n - 1, Mod);    //tmp.print();    ans = mul_mod(tmp, beg, Mod);    int res = ans.mat[0][0];    printf("Case #%d: %d\n", ++tt, res);}int main(){    cin >> t;    while (t--) solve();    return 0;}