转载:http://www.cnblogs.com/wuwing/p/3754808.html
题目大意:问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)即为最终结果
Loriex:赤裸裸的矩乘
跪哭了orzzzzzzzzzz
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define FFF 20140518 struct node{ long long mar[15][15]; }sor; void init(int k) { memset(sor.mar,0,sizeof(sor.mar)); for(int i=1;i<=k;i++) { for(int j=i;j<=k;j++) { sor.mar[i][j]=1; } if(i>1) { sor.mar[i][i-1]=k-i+2; } } } node marMulti(node a,node b,int k) { node ret; memset(ret.mar,0,sizeof(ret.mar)); for(int i=1;i<=k;i++) { for(int j=1;j<=k;j++) { for(int l=1;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,0,sizeof(ret.mar)); for(int i=1;i<=k;i++) ret.mar[i][i]=1; while(x) { if(x%2==1) ret=marMulti(now,ret,k); x/=2; now=marMulti(now,now,k); } return ret; } void print(node sor,int k) { for(int i=1;i<=k;i++) { for(int j=1;j<=k;j++) { cout<<sor.mar[i][j]<<' '; } cout<<endl; } } int main() { int keng,k,Case=1; long long n; scanf("%d",&keng); while(keng--) { scanf("%lld%d",&n,&k); init(k); node ret=matrixPow(n-1,k); int ans=0; // print(sor,k); // print(ret,k); for(int i=1;i<=k;i++) { ans+=(ret.mar[i][1]*(k+1))%FFF; ans%=FFF; } printf("Case #%d: %d\n",Case++,ans); } return 0; }