HDU3893之矩阵快速幂 - c++编程基础

TOP

HDU3893之矩阵快速幂

2014-11-23 21:12:53 来源: 作者: 【大中小】浏览:5次

Drawing Pictures
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 467 Accepted Submission(s): 207

Problem Description
Dr. Skywind is drawing a picture, using his favorite six colors, namely red, orange, yellow, green, blue, and violet.
The paper has N grids in a line. Each time he will fill a grid with one of the six colors. All grids needs to be filled. To make his drawing more beautiful, Skywind decided to draw symmetrically. Moreover, as he hates sorting, Skywind will never come up with the situation where all colors are in their original order. So he won't draw red-orange-yellow-green-blue-violet in a continuous way. And to make his drawing clearer, he won't paint the same color in adjacent grids.
Given N, you are asked to calculate the number of ways that Skywind can complete his drawing. As the answer might be very large, just output the number MOD 112233.

Input
There are multiple test cases ended with an EOF. Each test case will be a line containing one positive integer N. (N <= 10^9)

Output
For each test case, output the answer MOD 112233 in a single line.

Sample Input
2
5

Sample Output
0
150

题意：给n个格子用6种颜色去填,相邻颜色不能相同,不能1，2，3，4，5，6六种颜色连续在一起,前后要对称,求有多少种可能

/*分析:假设 
dp[i][0]表示长度为i的全部有效数 
dp[i][5]表示长度为i的以12345结尾的有效数(方便dp[i][0]减去654321xxx,123456xxx这种) 
dp[i][4]表示长度为i的以1234结尾的有效数(方便得到dp[i][5]) 
dp[i][3]表示长度为i的以123结尾的有效数(方便得到dp[i][4]) 
dp[i][2]表示长度为i的以12结尾的有效数(方便得到dp[i])[3] 
dp[i][1]表示长度为i的以1结尾的有效数(方便得到dp[i][2]) 
则: 
dp[i][0]=5*dp[i-1][0]-2*dp[i][5];//减去654321,123456这种 
dp[i][5]=dp[i-1][4]; 
dp[i][4]=dp[i-1][3]; 
dp[i][3]=dp[i-1][2] 
dp[i][2]=dp[i-1][1]; 
dp[i][1]=dp[i][0]-dp[i-1][1]-dp[i][5];//减去11xxx,123456xxx这种 
然后用矩阵快速幂求dp[n][0] 
*/  
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#define INF 99999999   
using namespace std;  
  
const int MAX=6;  
const int mod=112233;  
__int64 array[MAX][MAX],sum[MAX][MAX];  
  
void MatrixMult(__int64 a[MAX][MAX],__int64 b[MAX][MAX]){  
    __int64 c[MAX][MAX]={0};  
    for(int i=0;i>=1;  
    }  
    return ((sum[0][0]*6+sum[0][5])%mod+mod)%mod;//dp[1][0]=6,dp[1][1]=1,dp[1][i]=0(i != 1 && i != 0)   
}  
  
int main(){  
    int n;  
    while(scanf("%d",&n)!=EOF){  
        if(n%2 == 0)printf("0\n");//偶数由于对称中间两个一定相等所以没有符合的    
        else{  
            n=n/2+1;  
            printf("%I64d\n",Matrix(n-1));//dp是从长度1开始,所以只需要矩阵相乘n-1次就是长度为n的结果    
        }  
    }  
    return 0;  
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：ZOJ 1589 Professor John ~Floyd..	下一篇：poj 2109 Power of Cryptography(..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: