HDU2604Queuing矩阵乘法.doc

HDU 2604 Queuing 矩阵乘法By baiyun 2011 年 8 月 9 日Posted in: ACM, 矩阵乘法题目的意思比较简单, 就是给出一组由1, 0 组成的长为 L 的序列, 其中不能出现”111 和 “101 子序列. 问这样的长L的序列有多少种.解题: 假设 S 是已有的合法序列, 那么它的后缀只能是 : F1 = 000, F2 = 001, F3 = 010, F4 = 100, F5 = 011, F6 = 110 中的一种, 现在往S后接一个字符, 有 2种选择 : 1 或者 0. 定义 DPNi 表示长为N的序列的第i种状态包含的合法序列的数目, 那么可以得到如下状态转移关系:DPN1 = DPN-11 + DPN-14;DPN2 = DPN-11 + DPN-14;DPN3 = DPN-12;DPN4 = DPN-13 + DPN-16;DPN5 = DPN-12;DPN6 = DPN-15;那么可以依此构造出矩阵 A , B = DP3 :这样, 就可以得到 DP4 = A * B , DP5 = A2 * B .最后用2分快速幂就能很快得到答案.#ifdef LOCAL #define SP system(pause); #define DBG Debug();#else #define SP #define DBG#endifvoid Debug () freopen ( 1.in, r, stdin );freopen ( 1.out, w, stdout );#define MEM(x,y) memset(x,y,sizeof(x)int N, M, K, fuck5;struct Mat int n, m, mat3333;Mat ( int nn = 0, int mm = 0 ) n = nn, m = mm;MEM(mat,0);Mat operator * ( const Mat &t ) /矩阵乘法Mat res ( n );for ( int i = 0; i n; + i ) for ( int j = 0; j n; + j ) for ( int k = 0; k n; + k ) res.matji += matjk * t.matki;res.matji %= M;return res;void print () /输出矩阵for ( int i = 0; i n; + i ) for ( int j = 0; j 1 );return k&1 ? res * res * A : res * res;void prs ( Mat &A, Mat &B, int n ) Mat res = Pow ( A, n );res = res * B;int sum = 0;for ( int i = 0; i 6; + i ) sum += res.mati0;printf ( %dn, sum % M );void init ( Mat &A, Mat &B ) /*初始化*/A.mat00 = A.mat03 = A.mat10 = A.mat13 = A.mat21 = 1;A.mat32 = A.mat35 = A.mat41 = A.mat54 = 1;for ( int i = 0; i 6; + i ) B.mati0 = 1;fuck0 = 0, fuck1 = 2, fuck2 = 4, fuck3 = 6;int main ()/DBGMat A ( 6 ), B ( 6 );init ( A, B );/*初始化基础矩阵 A B */while ( scanf ( %d%d, &N, &M ) != EOF ) if