傳送門：HUSTOJ
傳送門：HDU
n個人排隊，f表示女，m表示男，包含子串‘fmf’和‘fff’的序列為O隊列，否則為E隊列，有多少個序列為E隊列。
矩陣快速冪搞，遞推會掛。 板子。 %%%1 %%%2
我竟然忘了矩陣乘法不可交換。。
#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<vector>#include<cmath>#include<queue>#define _ ios_base::sync_with_stdio(0);cin.tie(0);using namespace std;const int MAXN=4;const int oo=0x3f3f3f3f;typedef long long LL;const LL loo=4223372036854775807ll;int MOD=0;struct Matrix{ int ma[MAXN][MAXN]; Matrix(){ memset(ma, 0, sizeof(ma)); } Matrix(Matrix &a) { for(int i=0;i<MAXN;i++) { for(int j=0;j<MAXN;j++) { ma[i][j]=a.ma[i][j]; } } }};Matrix Operator *(Matrix &a, Matrix &b){ Matrix c; for(int i=0;i<MAXN;i++) { for(int j=0;j<MAXN;j++) { for(int k=0;k<MAXN;k++) { c.ma[i][j]=(c.ma[i][j]+(a.ma[i][k]*b.ma[k][j])%MOD)%MOD; } } } return c;}Matrix operator ^(Matrix &a, int m){ Matrix t; for(int i=0;i<MAXN;i++) t.ma[i][i]=1; while(m) { if(m&1) t=a*t; a=a*a; m>>=1; } return t;}int main(){_ int L; while(cin>>L>>MOD) { Matrix a, b, c; a.ma[0][0]=9;a.ma[1][0]=6;a.ma[2][0]=4;a.ma[3][0]=2; b.ma[0][0]=b.ma[0][2]=b.ma[0][3]=b.ma[1][0]=b.ma[2][1]=b.ma[3][2]=1; if(L==0) cout<<0<<endl; else if(L<=4) cout<<a.ma[4-L][0]%MOD<<endl; else { L-=4; c=b^L; c=c*a; cout<<c.ma[0][0]<<endl; } } //system("pause"); return 0;}新聞熱點
疑難解答
