首页 > 代码库 > 北邀 E Elegant String
北邀 E Elegant String
E. Elegant String
1000ms
1000ms
65536KB
64-bit integer IO format: %lld Java class name: Main
Font Size:
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
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 typedef long long LL; 7 8 const LL p = 20140518; 9 struct Matrix 10 { 11 LL mat[11][11]; 12 void init() 13 { 14 memset(mat,0,sizeof(mat)); 15 } 16 void first(int n) 17 { 18 int i,j; 19 for(i=1;i<=n;i++) 20 for(j=1;j<=n;j++) 21 if(i==j)mat[i][j]=1; 22 else mat[i][j]=0; 23 } 24 }M_hxl,M_tom; 25 Matrix multiply(Matrix cur,Matrix ans,int n) 26 { 27 Matrix now; 28 now.init(); 29 int i,j,k; 30 for(i=1;i<=n;i++) 31 { 32 for(k=1;k<=n;k++) 33 { 34 for(j=1;j<=n;j++) 35 { 36 now.mat[i][j]=now.mat[i][j]+cur.mat[i][k]*ans.mat[k][j]; 37 now.mat[i][j]%=p; 38 } 39 } 40 } 41 return now; 42 } 43 Matrix pow_mod(Matrix ans,LL n,LL m) 44 { 45 Matrix cur; 46 cur.first(m); 47 while(n) 48 { 49 if(n&1) cur=multiply(cur,ans,m); 50 n=n>>1; 51 ans=multiply(ans,ans,m); 52 } 53 return cur; 54 } 55 LL solve(LL n,LL k) 56 { 57 M_hxl.init(); 58 int i,j; 59 for(i=1;i<=k-1;i++)M_hxl.mat[1][i]=1; 60 for(i=2;i<=k-1;i++) 61 { 62 for(j=1;j<=k-1;j++) 63 { 64 if(i-j>1)continue; 65 if(i-j==1) M_hxl.mat[i][j]=k-i+1; 66 else M_hxl.mat[i][j]=1; 67 } 68 }/**ok**/ 69 M_tom = pow_mod(M_hxl,n,k-1); 70 LL sum=(M_tom.mat[1][1]*k)%p; 71 return sum; 72 73 } 74 int main() 75 { 76 int T,t; 77 LL n,k; 78 scanf("%d",&T); 79 for(t=1;t<=T;t++) 80 { 81 scanf("%lld%lld",&n,&k); 82 k++; 83 LL ans=solve(n,k); 84 printf("Case #%d: %lld\n",t,ans); 85 } 86 return 0; 87 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。