Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 4036 | Accepted: 1799 |
Description
Panda has received an assignment of painting a line of blocks. Since Panda is such an intelligent boy, he starts to think of a math problem of painting. Suppose there are N blocks in a line and each block can be paint red, blue, green or yellow. For some myterious reasons, Panda want both the number of red blocks and green blocks to be even numbers. Under such conditions, Panda wants to know the number of different ways to paint these blocks.
Input
The first line of the input contains an integer T(1≤T≤100), the number of test cases. Each of the next T lines contains an integer N(1≤N≤10^9) indicating the number of blocks.
Output
For each test cases, output the number of ways to paint the blocks in a single line. Since the answer may be quite large, you have to module it by 10007.
Sample Input
2 1 2
Sample Output
2 6
题意:
给出 T(1 ~ 100),代表有 T 个样例,后给出 N(1 ~ 10 ^ 9),代表有 N 个格子。给每个格子填色,可以填红蓝绿黄四种颜色,求染成红色和绿色同时为偶数的染色方案个数。结果模 10007。
思路:
矩阵快速幂。书上例题。设 ai 为同时为偶数的方法数,bi 为一个为偶数一个为奇数的方法数, ci 为同时为奇数的方法数,所以:
ai+1 = 2 x ai + bi ;
bi+1 = 2 x ai + 2 x bi + 2 x ci ;
ci+1 = bi + 2 x ci;
于是可以生成矩阵:
ai+1 2 1 0 ai ai 2 1 0 1
( bi+1 ) = ( 2 2 2 ) x ( bi ) -> ( bi ) = ( 2 2 2 ) ^ i X ( 0 )
ci+1 0 1 2 ci ci 0 1 2 0
最后得出来的矩阵中的 A [ 0 ] [ 0 ] 就是答案。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef vector<int> vec; typedef vector<vec> mat; const int MOD = 10007; mat mul (mat a, mat b) { mat c(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]) % MOD; } } } return c; } mat pow (mat a, int n) { mat b(a.size(), vec(a[0].size())); for (int i = 0; i < a.size(); ++i) { b[i][i] = 1; } while (n > 0) { if (n & 1) b = mul(b, a); a = mul(a, a); n >>= 1; } return b; } int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); mat a(3, vec(3)); 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; a = pow(a, n); printf("%d\n", a[0][0]); } return 0; }
相关推荐
该教程讲述Code Blocks的入门知识,Code Blocks 是开源的C及C++编程环境
这是一个编译过后的scratch-blocks源码,可以直接使用 如果不能直接下载请私信我。
Code::Blocks的教程,因为基本都是英文版,所以有些功能有中文教程还是比较好用的
Built-In Building Blocks.dotx office2016 .
intel thread building blocks
code blocks
Embedded Systems Building Blocks
原来只有sqlserver的oracleMicrosoft.ApplicationBlocks.Data 现在oracle版的也有了
ios Blocks 编程要点 深层 详细讲解
Code::Blocks 17.12 中文版 汉化方法: 1.关闭Code::Blocks 2.将share文件夹覆盖到Code::Blocks根目录下 3.打开Code::Blocks 4.依次点击Settings --> Environment... -->View 5 .将第二个选项...
code blocks 10.05的中文语言包,加上每日提示双语(中英文)
Building Blocks.dotx为word2007的页码模板,亲测有效,安装方法百度下即可
Blocks Programming Topics
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
我的世界MOD快速建造方块,1.5.2的快来下下下在啊,妈妈说标题长才有人看
Stack Blocks - A Unity 3d Game The game is inspired from the game "Stack" . Screenshots
TBB,Thread Building Blocks,线程构建模块
这是关于Code::Blocks的一些中文文档,对Code::Blocks感兴趣的童鞋可以下载学习。