`

HDU 3893 Drawing Pictures

阅读更多
/*
*  [题意]
*   有n个格子需要填色,有6种颜色(设为123456),要求:
*       1、填完后要对称
*       2、相邻不能同色
*       3、不可出现123456的情况
*  [解题方法]
*   由于是对称所以只要处理前(n+1)/2个,翻过去即可(注意此时不可出现654321,因为要翻过去)
*   即令n=(n+1)/2求解即可
*!设f(n,x):长度为n的以x结尾的合法颜色串个数
*   所以由题意得:
*       1、f(n,1) = f(n-1,2)+f(n-1,3)+f(n-1,4)+f(n-1,5)+f(n-1,6) - f(n-1,65432)
*       2、f(n,2) = f(n-1,1)+f(n-1,3)+f(n-1,4)+f(n-1,5)+f(n-1,6)
*       3、f(n,3) = f(n-1,1)+f(n-1,2)+f(n-1,4)+f(n-1,5)+f(n-1,6)
*       4、f(n,4) = f(n-1,1)+f(n-1,2)+f(n-1,3)+f(n-1,5)+f(n-1,6)
*       5、f(n,5) = f(n-1,1)+f(n-1,2)+f(n-1,3)+f(n-1,4)+f(n-1,6)
*       6、f(n,6) = f(n-1,1)+f(n-1,2)+f(n-1,3)+f(n-1,4)+f(n-1,5) - f(n-1,12345)
*
*       7、f(n,12) = f(n-1,1)
*       8、f(n,123) = f(n-1,12)
*       9、f(n,1234) = f(n-1,123)
*       10、f(n,12345) = f(n-1,1234)
*
*       11、f(n,65) = f(n-1,6)
*       12、f(n,654) = f(n-1,65)
*       13、f(n,6543) = f(n-1,654)
*       14、f(n,65432) = f(n-1,6543)
*
*   所以有矩阵:
*       |0 1 1 1 1 1 0 0 0 0  0 0 0 -1|       |f(n-1,1)     |       |f(n,1)     |
*       |1 0 1 1 1 1 0 0 0 0  0 0 0 0 |       |f(n-1,2)     |       |f(n,2)     |
*       |1 1 0 1 1 1 0 0 0 0  0 0 0 0 |       |f(n-1,3)     |       |f(n,3)     |
*       |1 1 1 0 1 1 0 0 0 0  0 0 0 0 |       |f(n-1,4)     |       |f(n,4)     |
*       |1 1 1 1 0 1 0 0 0 0  0 0 0 0 |       |f(n-1,5)     |       |f(n,5)     |
*       |1 1 1 1 1 0 0 0 0 -1 0 0 0 0 |       |f(n-1,6)     |       |f(n,6)     |
*       |1 0 0 0 0 0 0 0 0 0  0 0 0 0 |   *   |f(n-1,12)    |   =   |f(n,12)    |
*       |0 0 0 0 0 0 1 0 0 0  0 0 0 0 |       |f(n-1,123)   |       |f(n,123)   |
*       |0 0 0 0 0 0 0 1 0 0  0 0 0 0 |       |f(n-1,1234)  |       |f(n,1234)  |
*       |0 0 0 0 0 0 0 0 1 0  0 0 0 0 |       |f(n-1,12345) |       |f(n,12345) |
*       |0 0 0 0 0 1 0 0 0 0  0 0 0 0 |       |f(n-1,65)    |       |f(n,65)    |
*       |0 0 0 0 0 0 0 0 0 0  1 0 0 0 |       |f(n-1,654)   |       |f(n,654)   |
*       |0 0 0 0 0 0 0 0 0 0  0 1 0 0 |       |f(n-1,6543)  |       |f(n,6543)  |
*       |0 0 0 0 0 0 0 0 0 0  0 0 1 0 |       |f(n-1,65432) |       |f(n,65432) |
*   答案 = f(n,1) + f(n,2) + f(n,3) + f(n,4) + f(n,5) + f(n,6)
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define M 15
#define LL long long
#define FF(i, n) for(int i = 0; i < n; i++)

int ans[M], mod = 112233;
int ret[M][M], C[M][M];
int init[M][M];

void ini()
{
    memset(ans, 0, sizeof(ans));
    memset(init, 0, sizeof(init));
    FF(i, 6) {
        ans[i] = 1;
        FF(j, 6) if (i != j) init[i][j] = 1;
    }
    init[5][9] = -1;
    init[6][0] = init[7][6] = init[8][7] = init[9][8] = 1;
    init[0][13] = -1;
    init[10][5] = init[11][10] = init[12][11] = init[13][12] = 1;
}

void matmul(int a[][M], int b[][M], int n)
{
    int tp[M][M] = {0};
    FF(i, n) FF(k, n) if(a[i][k]) FF(j, n) if(b[k][j])
        tp[i][j] = (tp[i][j] + (LL)a[i][k]*b[k][j]) % mod;
    FF(i, n) FF(j, n) a[i][j] = tp[i][j];
}

void matmul(int a[], int b[][M], int n)
{
    int tp[M] = {0};
    FF(j, n) if(a[j]) FF(i, n) if(b[i][j])
        tp[i] = (tp[i] + (LL)b[i][j]*a[j]) % mod;
    FF(i, n) a[i] = tp[i];
}

void qmod(int n, int b)
{
    FF(i, n) FF(j, n) ret[i][j] = (i==j);
    for ( ; b; b >>= 1)
    {
        if (b & 1) matmul(ret, init, n);
        matmul(init, init, n);
    }
}

int main()
{
    int n;
    while (cin >> n)
    {
        if (n % 2 == 0) {
            puts("0");
            continue;
        }
        n /= 2;
        ++n;
        ini();
        qmod(14, n-1);
        matmul(ans, ret, 14);
        int sum = 0;
        FF(i, 6) sum = (sum + ans[i]) % mod;
        cout << (sum+mod)%mod << endl;
    }
    return 0;
}

 

1
4
分享到:
评论

相关推荐

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    hdu2101解决方案

    hdu2101AC代码

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

    HDU acm-PPT课件

    【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...

    hdu acm1166线段树

    hdu 1166线段树代码

    HDU最全ac代码

    HDU(Hangzhou Dianzi University)是国内外知名的在线编程竞赛平台,主要服务于ACM/ICPC(国际大学生程序设计竞赛)以及相关的算法训练。"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码...

    HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu.

    【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

Global site tag (gtag.js) - Google Analytics