POJ 3734

に言及
n個の板の4種類の色(赤と緑と青と黄)があって、n個の板に対して色を塗って、赤と緑の板がすべて偶数個であることを確保する情況の下で何種類の色の方案(10007に対して型を取ります)があります
n<1e9
 
まず暴力捜索は考えなくてもいいですが、この問題をするにはdpつまりプッシュする方法が必要です.現在のn枚の板について全部でいくつかの状況があると思いますか.
An:赤と緑が偶数になりました
Bn:赤か緑だけが偶数に達した
Cn:すべて偶数個に達していません
DPの考え方が既知の状況から未知の状況を推測する以上,An+1 Bn+1 Cn+1に対して既知の情報で推測することができる.
Ai+1=2*Ai(次は赤と緑と青と黄の2つを塗らない場合)+Bi(その色がどの色を塗らない場合)
Bi+1=2*Ai(赤または緑を任意に塗る)+2*Bi(青または黄を任意に塗る)+2*Ci(赤または緑を任意に塗る)
Ci+1=Bi(偶数個集めてその色を塗る)+2*Ci(青か黄を塗る)
これで3つのプッシュ式ができました
前に見たフィボナッチ数列問題を思い出す法則を見つけたようだが,この問題も行列の性質を利用して迅速に完成することができる.
縦は「AiBi Ci」で3*3行列が必要ですが、プッシュ式を見るとこの行列を出すのは難しくありません.
          [    2    1    0    ]
X=[2 2 2 2]そして高速べき乗を用いて素早く解くことができる結果を第1列に記録し,第1列の第1行はAiである.
          [     0    1    2    ]
 
MACコードは以下の通りです:(今回はリロード演算子を試してみました)
 

    #include
    #include
    using namespace std;
    const int mod = 1e4+7;
    struct matrix
    {
        int m[3][3];
        matrix friend operator * (matrix a,matrix b)
	    {
		matrix tp;
		memset(tp.m,0,sizeof(tp.m));
		for(int i=0;i<3;++i)
		{
			for(int j=0;j<3;++j)
			{
				if(!a.m[i][j])
				{
					continue;
				}
				for(int k=0;k<3;++k)
				{
					tp.m[i][k]+=(a.m[i][j]*b.m[j][k])%mod;
					tp.m[i][k]%=mod;
				}
			}
		}
		return tp;
	    }
    };
    matrix base;
    int pow(matrix x,int n)
    {
        matrix ans={0};
	    for(int i=0;i<3;++i)
	    {
	 	    ans.m[i][i]=1;
	    }
        while(n)
        {
            if(n&1)
                ans = ans * x;
            x = x * x;
            n>>=1;
        }
        return ans.m[0][0];
    }
    int n;
    int main()
    {
        int test;
        cin>>test;
        while(test--)
        {
            cin>>n;
            matrix base={2,1,0,2,2,2,0,1,2};
            cout<