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，這樣相當於這個子串已經安全（近似安全）了。

所以就是規劃問題了。

用dp[i][j]表示字符串增長到第i位時，已經有j位安全的數量。

轉移方程：

所以就是矩陣快速冪的計算了。

既然都走到這步了，矩陣也就很好寫了：<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PGltZyBzcmM9"http://www.2cto.com/uploadfile/Collfiles/20140523/20140523091449228.gif" alt="\">

最後的結果就是

res就是答案了。

代碼示例

/****
	*@author    Shen
	*@title     ±±¾©ÑûÇëÈüE
	*/
#include 
#include 
#include 
#include 
#include 
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;
}