题目链接：http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=34985
题目大意：问n长度的串用0~k的数字去填，有多少个串保证任意子串中不包含0~k的某一个全排列
邀请赛上A的较多的一道题，比赛的时候死活想不出，回来之后突然就想通了，简直..... = =!
解题思路：
对于所有串我们都只考虑末尾最多有多少位能构成全排列的一部分（用l来表示），即最多有多少位不重复的数字出现，将问题转化为求末尾最多有k位能构成全排列的串的总数量
假设k为5，有一个串……0023，不难发现l=3
我们以这个串出发在之后添上数字，假如我们添的是0、2、3中的一个：
0: ……00230 (l=3)
2: ……00232 (l=2)
3: ……00233 (l=1)
假如是l长度中没有出现过的数字
则构成新串 ……00231 ……00234 ……00235 l=4
最后可以得到规律：总长度为n串中 l=m的串的数量 x1 得到 总长度为n+1的串中 l=(1,2,……,m)的串
总长度为n串中 l=m的串的数量 x(k-m+2) 得到 总长度为n+1的串中 l=m+1的串
用mar[i][j]来表示由l=j的串得到l=i的串所以
mar可以表示为（以k=5为例）
1 1 1 1 1
5 1 1 1 1
0 4 1 1 1
0 0 3 1 1
0 0 0 2 1
通过该矩阵我们可以由长度为n的串数量可以推出长度为n+1的串的数量：
于是我们可以通过长度1的串最终得到总长度为n的串， n=1时只有l最多为1 总数为 k+1
快速幂求得该矩阵的(n-1)次幂，该矩阵的第一列相加乘（k+1）即为最终结果
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define FFF 20140518
struct node{
long long mar[][];
}sor;
void init(int k)
{
memset(sor.mar,,sizeof(sor.mar));
for(int i=;i<=k;i++)
{
for(int j=i;j<=k;j++)
{
sor.mar[i][j]=;
}
if(i>)
{
sor.mar[i][i-]=k-i+;
}
}
}
node marMulti(node a,node b,int k)
{
node ret;
memset(ret.mar,,sizeof(ret.mar));
for(int i=;i<=k;i++)
{
for(int j=;j<=k;j++)
{
for(int l=;l<=k;l++)
{
ret.mar[i][j]+=(a.mar[i][l]*b.mar[l][j])%FFF;
ret.mar[i][j]%=FFF;
}
}
}
return ret;
}
node matrixPow(long long x,int k)
{
node now=sor;
node ret;
memset(ret.mar,,sizeof(ret.mar));
for(int i=;i<=k;i++)
ret.mar[i][i]=;
while(x)
{
if(x%==)
ret=marMulti(now,ret,k);
x/=;
now=marMulti(now,now,k);
}
return ret;
}
void print(node sor,int k)
{
for(int i=;i<=k;i++)
{
for(int j=;j<=k;j++)
{
cout<<sor.mar[i][j]<<' ';
}
cout<<endl;
}
}
int main()
{
int keng,k,Case=;
long long n;
scanf("%d",&keng);
while(keng--)
{
scanf("%lld%d",&n,&k);
init(k);
node ret=matrixPow(n-,k);
int ans=;
// print(sor,k);
// print(ret,k);
for(int i=;i<=k;i++)
{
ans+=(ret.mar[i][]*(k+))%FFF;
ans%=FFF;
}
printf("Case #%d: %d\n",Case++,ans);
}
return ;
}