题目链接: http://poj.org/problem?id=3734
题意: 给出 n 个排成一列的方块, 用红, 蓝, 绿, 黄四种颜色给它们染色, 求染成红, 绿的方块个数同时为偶数的方案数模 10007 的值.
题解: 这是 WC2019 第二课堂生成函数的题, 实际上可以不用生成函数, 我们考虑如下状态: a[i] 表示前 i 个中红, 绿均为偶的方案数, b[i] 表示其中一个为奇数的方案数, c[i] 表示都为奇数的方案数. 然后可以这样转移: a[i]=2a[i-1]+b[i-1],b[i]=2a[i-1]+2b[i-1]+2c[i-1],c[i]=2c[i-1]+b[i-1], 由于 n<=1e9, 所以用矩阵优化即可, 复杂度 O(27qlogn)
备注: 由于 POJ 编译器太垃圾, 矩阵乘法传输数组会 CE, 所以代码很长.
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- const int mod=10007;
- int n,a[4][4],ret[4][4],c[4][4];
- int main()
- {
- int T;scanf("%d",&T);
- while(T--)
- {
- scanf("%d",&n);
- for(int i=0;i<3;i++)
- for(int j=0;j<3;j++)
- ret[i][j]=(i==j);
- a[0][0]=2,a[0][1]=1,a[0][2]=0;
- a[1][0]=2,a[1][1]=2,a[1][2]=2;
- a[2][0]=0,a[2][1]=1,a[2][2]=2;
- while(n)
- {
- if(n&1)
- {
- for(int i=0;i<3;i++)
- for(int j=0;j<3;j++)
- {
- c[i][j]=0;
- for(int k=0;k<3;k++)c[i][j]=(c[i][j]+ret[i][k]*a[k][j])%mod;
- }
- for(int i=0;i<3;i++)
- for(int j=0;j<3;j++)
- ret[i][j]=c[i][j];
- }
- for(int i=0;i<3;i++)
- for(int j=0;j<3;j++)
- {
- c[i][j]=0;
- for(int k=0;k<3;k++)c[i][j]=(c[i][j]+a[i][k]*a[k][j])%mod;
- }
- for(int i=0;i<3;i++)
- for(int j=0;j<3;j++)
- a[i][j]=c[i][j];
- n>>=1;
- }
- printf("%d\n",ret[0][0]);
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-2935738.html