hdu5411
这道题一开始用动规做,超时,因为N*M的复杂度太大了,后来,根据题解,知道,动规,就是一种递推过程,一般可以转化为矩阵乘法,斐波那契数的一种求解方式就是如此,然后就是根据动态转移方程构造矩阵,对于这道题来说,需要长度为0,长度为1,长度为2……的种数加起来,所以在构造时需要考虑在内。这样,这道题就可以在1s内求得答案了。所以,如果下次动规超时时,可以向这方面想一下。
2015.8.29:
这道题也是前几天作为沟通练习给队友讲过,就是构造矩阵,构造矩阵需要多练习。
(食堂的牛肉拉面里面的白萝卜去哪了?)
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; #define N 60 #define MOD 2015 struct matix{ int ma[N][N]; matix(){ for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ ma[i][j]=0; } } } matix operator *(const matix another){ matix ans; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ for(int k=0;k<N;k++){ ans.ma[i][k]=(ans.ma[i][k]+ma[i][j]*another.ma[j][k])%MOD; } } } return ans; } }; matix pow(matix x,int y){ matix ans; for(int i=0;i<N;i++){ ans.ma[i][i]=1; } while(y){ //printf("wo shi da hao ren"); if(y%2){ ans=ans*x; } x=x*x; y=y/2; } return ans; } int main(){ int t; int n,m; int cou; int a; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); matix now; for(int i=1;i<=n;i++){ scanf("%d",&cou); for(int j=1;j<=cou;j++){ scanf("%d",&a); now.ma[i-1][a-1]=1; } } for(int i=0;i<=n;i++){ now.ma[i][n]=1; } for(int i=0;i<n;i++){ now.ma[n][i]=0; } /*for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ printf("%d ",now.ma[i][j]); } printf("\n"); }*/ now=pow(now,m-1); //printf("%d\n",m-1); /*for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ printf("%d ",now.ma[i][j]); } printf("\n"); }*/ int ans=1; for(int i=0;i<n;i++){ for(int j=0;j<=n;j++){ ans=(ans+now.ma[i][j])%MOD; } } printf("%d\n",ans); } }