Main » 2013 October 8 » 多米诺难题
1:03 PM 多米诺难题 |
状态压缩dp+矩阵加速#include<cstdio> #include<cstring> #include<iostream> #define N 5 using namespace std; typedef long long LL; int m,n,p; struct matrix { int Matrix[32][32]; matrix operator*(const matrix b) { int i,j,k; matrix c; memset(c.Matrix,0,sizeof(c.Matrix)); for (i=0;i<(1<<m);i++) for (j=0;j<(1<<m);j++) for (k=0;k<(1<<m);k++) c.Matrix[i][j]=((Matrix[i][k]*b.Matrix[k][j])%p+c.Matrix[i][j])%p; return c; } matrix power(int x) { if (x<2) return *this; matrix mt=power(x/2); if (x%2) return mt*mt*(*this); else return mt*mt; } }; matrix m1; int anstot=0; int t[32]; void DFS(int a,int F0) { m1.Matrix[a][F0]=1; int i; for (i=0;i<m-1;i++) if ((F0+(3<<i))==(F0|(3<<i))) DFS(a,F0+(3<<i)); return; } void DFS0(int F0) { t[F0]=1; int i; for (i=0;i<m-1;i++) if ((F0+(3<<i))==(F0|(3<<i))) DFS0(F0+(3<<i)); return; } void init(int a) { int cnt=m+1,i,tot,F0=0,att=a,f[7]; memset(f,0,sizeof(f)); while (a>0){cnt--;f[cnt]=a%2;a/=2;} for (i=1;i<=m;i++) tot+=f[cnt]; if (tot==m){m1.Matrix[a][0]=1;return;} for (i=1;i<=m;i++) if (f[i]==0) F0+=1<<(m-i); DFS(att,F0); } int main() { cin>>n>>m>>p; memset(m1.Matrix,0,sizeof(m1.Matrix)); memset(t,0,sizeof(t)); int i; for (i=0;i<(1<<m);i++) init(i); DFS0(0); cout<<m1.power(n).Matrix[(1<<m)-1][(1<<m)-1]<<endl; return 0; } |
|
|
| Total comments: 0 | |