首页 > ACM题库 > HDU-杭电 > HDU 3893-Drawing Pictures[解题报告]HOJ
2015
04-13

HDU 3893-Drawing Pictures[解题报告]HOJ

Drawing Pictures

问题描述 :

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.

输入:

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

输出:

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

样例输入:

2
5

样例输出:

0
150

题意:给一串长度为N的小方格上色,一共有六种颜色分别是
red, orange, yellow, green, blue, violet
。要求 1.左右两边颜色对称 2.相邻的小方格颜色不同 3.连续的六个小方格的颜色不能依次是 red, orange, yellow, green, blue, violet,求一共有多少种上色方法。(N<=10^9)

解法:
    如果N为偶数,不可能满足条件。因为如果N为偶数,要满足第一个条件,中间两个格子颜色必然相同,这会导致不能满足第二个条件。
    如果N为奇数,我们只需要考虑前面(N+1)/2个格子的着色方法数,后面的格子因为要和前面的格子对称,所以不需要考虑。
    我们假设六种颜色代号分别是 012345,因为有第三个条件,所以前面(N+1)/2个格子颜色不能出现
012345 序列,
由于对称也不能出现 543210 序列。
定12个状态,分别为 [],[0],[5],[01],[54],[012],[543],[0123],[5432],[01234],[54321],[------]。
状态转移矩阵为:
    3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 3, 0,
    1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
    1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0,
    0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 5

#include <stdio.h>
#include <memory.h>

const __int64 mod = 112233;

__int64 init_mtx[12][12] = {
    3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 3, 0,
    1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
    1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0,
    0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 5
};
__int64 init_cunt[12] = {
    4, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

__int64 mtx1[12][12], mtx2[12][12], mtx3[12][12];

void mul(__int64 mtxa[12][12], __int64 mtxb[12][12]) {
    int i, j, k;

    for (i = 0; i < 12; i++) {
        for (j = 0; j < 12; j++) {
            mtx3[i][j] = 0;
            for (k = 0; k < 12; k++)
                mtx3[i][j] += mtxa[i][k] * mtxb[k][j];
            mtx3[i][j] %= mod;
        }
    }
    memcpy(mtxa, mtx3, sizeof(mtx3));
}

void solve(int m) {
    int i, j;

    memset(mtx1, 0, sizeof(mtx1));
    for (i = 0; i < 12; i++)
        mtx1[i][i] = 1;
    memcpy(mtx2, init_mtx, sizeof(mtx2));
    
    while (m) {
        if (m & 1)
            mul(mtx1, mtx2);
        mul(mtx2, mtx2);
        m >>= 1;
    }

    long long ans = 0;
    for (i = 0; i < 11; i++)
        for (j = 0; j < 11; j++)
            ans += mtx1[i][j] * init_cunt[j];
    printf("%I64d\n", ans % mod);
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n % 2 == 0) printf("0\n");
        else solve(n / 2);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/racebug2010/article/details/6657902


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥