首页 > 代码库 > bnuoj 34985 Elegant String

bnuoj 34985 Elegant String

题目链接:http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=34985

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
2
1 1
7 6
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.
Case #1: 2
Case #2: 818503
source:2014 ACM-ICPC Beijing Invitational Programming Contest
 
题意:首先定义一个串elegant string:在这个串里的任何子串都没有包括0~k的一个全排列,现在给出n和k,要求求出长度为n的elegant string的个数。
解法:DP+矩阵快速幂。我们先用DP推出递推公式,然后用矩阵快速幂解决这个公式。具体思想如下:
定义DP数组:dp[12][12](dp[i][j]表示长度为 i 时字符串末尾连续有 j 个不同数字,例:1233末尾只有一个数字3,2234末尾有3个:2,3,4)。
以第二组数据为例:n=7   k=6
 
初始化:dp[1][1]=k+1,dp[1][2,,,k]=0;
dp[i+1][1]=dp[i][1]+dp[i][2]+dp[i][3]+dp[i][4]+dp[i][5]+dp[i][6]
dp[i+1][2]=6*dp[i][1]+dp[i][2]+dp[i][3]+dp[i][4]+dp[i][5]+dp[i][6]
dp[i+1][3]=5*dp[i][2]+dp[i][3]+dp[i][4]+dp[i][5]+dp[i][6]
dp[i+1][4]=4*dp[i][3]+dp[i][4]+dp[i][5]+dp[i][6]
dp[i+1][5]=3*dp[i][4]+dp[i][5]+dp[i][6]
dp[i+1][6]=2*dp[i][5]+dp[i][6]
把递推式改为如下矩阵:
技术分享
 
然后我们就可以用快速幂来解决了
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #define inf 0x7fffffff 8 using namespace std; 9 typedef long long ll;10 const int maxn=12;11 const ll mod=20140518;12 13 ll n,k;14 struct matrix15 {16     ll an[maxn][maxn];17 }A,B;18 matrix multiply(matrix x,matrix y)19 {20     matrix sum;21     memset(sum.an,0,sizeof(sum.an));22     for (int i=1 ;i<=k ;i++)23     {24         for (int j=1 ;j<=k ;j++)25         {26             for (int k2=1 ;k2<=k ;k2++) {27                 sum.an[i][j]=(sum.an[i][j]+x.an[i][k2]*y.an[k2][j]%mod);28                 if (sum.an[i][j]>=mod) sum.an[i][j] -= mod;29             }30         }31     }32     return sum;33 }34 matrix power(ll K,matrix q)35 {36     matrix temp;37     for (int i=1 ;i<=k ;i++)38     {39         for (int j=1 ;j<=k ;j++)40         temp.an[i][j]= i==j ;41     }42     while (K)43     {44         if (K&1) temp=multiply(temp,q);45         q=multiply(q,q);46         K >>= 1;47     }48     return temp;49 }50 int main()51 {52     int t,ncase=1;53     scanf("%d",&t);54     while (t--)55     {56         scanf("%lld%lld",&n,&k);57         if (n==1)58         {59             printf("Case #%d: %d\n",ncase++,k+1);continue;60         }61         matrix q;62         for (int i=1 ;i<=k ;i++)63         {64             for (int j=1 ;j<=k ;j++)65             {66                 if (j>=i) q.an[i][j]=(ll)1;67                 else if (j==i-1) q.an[i][j]=(ll)(k+2-i);68                 else q.an[i][j]=(ll)0;69             }70         }71         q=power(n-1,q);72 //        for (int i=1 ;i<=k ;i++)73 //        {74 //            for (int j=1 ;j<=k ;j++)75 //            cout<<q.an[i][j]<<" ";76 //            cout<<endl;77 //        }78         ll ans=0;79         for (int i=1 ;i<=k ;i++)80         {81             ans=(ans+(ll)q.an[i][1]*(ll)(k+1))%mod;82         }83         printf("Case #%d: %lld\n",ncase++,ans);84     }85     return 0;86 }

 

 
 
 
 
后续:感谢提出宝贵的意见。。。。
 

bnuoj 34985 Elegant String