网站开发技术分享ppt,免费网站建设自带后台管理程序,海原网站建设,广西网络营销外包公司一、题目大意
我们要给排成一行的区块涂颜色#xff0c;可以选择红、绿、蓝、黄四种#xff0c;要求红和绿的块都必须是偶数个#xff0c;求出最终的涂色方式#xff0c;对10007取余。
二、解题思路
我们设三个数列A#xff0c;B和C#xff1a;
1、A代表红色和绿色都…一、题目大意
我们要给排成一行的区块涂颜色可以选择红、绿、蓝、黄四种要求红和绿的块都必须是偶数个求出最终的涂色方式对10007取余。
二、解题思路
我们设三个数列AB和C
1、A代表红色和绿色都为偶数的组合数。
2、B代表红色为奇数绿色为偶数的组合数。
3、C代表红色和绿色都为奇数的组合数。 题目给出A[1]2,A[2]6,接下来我们推理A[3]和A[N]
当第一块不是红和绿时有 A[2] * 2种
当第一块是红色时剩下的需要让红色为奇数个且绿色为偶数个那么剩下的直接按照B[2]的排列方式即可。
当第一块为绿色时剩下的需要让绿色为奇数个且红色为偶数个这种情况在数值上和B[2]相等。
则 A[3] A[2] * 2 B[2] * 2
同时不难看出A[2] A[1] * 2 B[1] * 2
所以 A[3] A[1] * (2 ^ 2) B[1] * (2 ^ 2) B[2] * 2代入A[1]2
A[3] 2 ^ 3 B[1] * (2 ^ 2) B[2] * 2
推出A[N] 2 ^ N B[1] * (2 ^ (N - 1)) B[2] * (2 ^ (N - 2)) ... B[N-1] * (2 ^ 1) A[N-1] * 2 B[N-1] * 2 接下来再来推C数列不难看出C[1] 0,C[2] 2接下来推 C[3] 和 C[N]
当第一块不为红色和绿色时排列数为 2 * C[2]。
当第一块为绿色时剩余的块需要绿色为偶数红色为奇数即B[2]种。
当第二块为红色时剩余的块需要红色为偶数且绿色为奇数这种情况数值上等于B[2]
则C[3] C[2] * 2 B[2] * 2
同理C[4] C[3] * 2 B[3] * 2
不难看出 C[2] 也等于 C[1] * 2 B[1] * 2
我们把C[1] 0代入C[2]个式子
C[2] B[1] * 2
把 C[2] 待入 C[3] 的式子
C[3] B[1] * (2 ^ 2) B[2] * 2
把 C[3] 带入 C4 的式子
C[4] B[1] * (2 ^ 3) B[2] * (2 ^ 2) B[3] * 2
则C[N] B[1] * (2 ^ (N - 1)) B[2] * (2 ^ (N - 2)) ... B[N-1] * (2 ^ 1) A[N] - 2 ^ N 接下来我们来推理数列B不难看出 B[1] 1B[2] 2接下来推理 B[3]和 B[N]
首先考虑第一块不为红色和绿色的情况剩余块需要有奇数个红色和偶数个绿色排列数为 B[2] * 2。
接下俩考虑第一块为红色的情况剩余块需要有偶数个红色和偶数个绿色则剩余块的排列数等于 A[2]。
接下来考虑第一块为绿色的情况剩余块需要有奇数个红色和奇数个绿色则剩余块的排列数等于C[2]。
那么B[3] B[2] * 2 A[2] C[2]
则 B[N] B[N-1] * 2 A[N-1] C[N-1]
同时C[N-1] A[N-1] - 2 ^ N
则可推出两个式子
式子1B[N] B[N-1] * 2 A[N-1] * 2 - 2 ^ N
式子2B[N1] B[N] * 2 A[N] * 2 - 2 ^ (N 1)
把A[N] A[N-1] * 2 B[N-1] * 2 代入式子2
式子2B[N1] B[N] * 2 A[N-1] * 4 B[N-1] * 4 - 2 ^(N 1)
把式子1乘以2
式子12 * B[N] B[N-1] * 4 A[N-1] * 4 - 2 ^ (N 1)
式子2减式子1得到式子3
式子3B[N1] - 2 * B[N] 2 * B[N]
则 B[N1] B[N] * 4 把 B[N 1] B[N] * 4且B1 1代入A的递推式
得出 A[N1] A[N] * 2 2 ^ (2 * N - 1)。
再把递推式写成矩阵的形式。 那么定义矩阵A为 2 1 // 0 4然后A A的 n - 1次幂
最终结果为(A[0][0] * 2 A[0][1] * 2) % M
三、代码
#include iostream
#include vector
using namespace std;
typedef vectorint vec;
typedef vectorvec mat;
const int M 10007;
mat mul(mat A, mat B)
{mat C mat(A.size(), vec(B[0].size()));for (int i 0; i A.size(); i){for (int j 0; j B[0].size(); j){for (int k 0; k B.size(); k){C[i][j] (C[i][j] A[i][k] * B[k][j]) % M;}}}return C;
}
mat pow(mat A, int N)
{mat B mat(A.size(), vec(A[0].size()));for (int i 0; i B.size(); i){B[i][i] 1;}while (N 0){if (N 1){B mul(B, A);}A mul(A, A);N 1;}return B;
}
void solve(int N)
{mat A mat(2, vec(2));A[0][0] 2;A[0][1] 1;A[1][1] 4;A pow(A, N - 1);int res (A[0][0] * 2 A[0][1] * 2) % M;printf(%d\n, res);
}
int main()
{int T, N;scanf(%d, T);while (T--){scanf(%d, N);solve(N);}return 0;
}
