Elegant String
Time Limit: 1000msMemory Limit: 65536KB 64-bit integer IO format: %lld Java class name: MainWe 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 6Sample Output
Case #1: 2 Case #2: 818503Source
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.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PGltZyBzcmM9"https://www.cppentry.com/upload_files/article/49/1_nanhk__.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; }