51Nod-1032-骨牌覆盖 V2

ACM模版

描述

题解

数据弱化的一个题,原题是 51Nod1033骨牌覆盖V251Nod 1033 骨牌覆盖 V2,插头 DPDP。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int MAXN = 1 << 5;

ll dp[MAXN][MAXN];
ll ret[MAXN][MAXN];
ll tmp[MAXN][MAXN];

int m, n = 3;

void dfs(int col, int pre, int now)
{
    if (col > n)
    {
        return ;
    }
    if (col == n)
    {
        dp[pre][now]++;
        return ;
    }

    dfs(col + 1, pre << 1, (now << 1) | 1);
    dfs(col + 1, (pre << 1) | 1, now << 1);
    dfs(col + 2, pre << 2 , now << 2);
}

void mul(ll ret[][MAXN], ll a[][MAXN], ll b[][MAXN])
{
    int t = 1 << n;
    for (int i = 0; i < t; i++)
    {
        for (int j = 0; j < t; j++)
        {
            ll tmp = 0;
            for (int k = 0; k < t; k++)
            {
                tmp += a[i][k] * b[k][j];
                tmp %= MOD;
            }
            ret[i][j] = tmp;
        }
    }
}

int main()
{
    scanf("%d", &m);

    dfs(0, 0, 0);

    int t = 1 << n;
    for (int i = 0; i < t; i++)
    {
        ret[i][i] = 1;
    }

    m++;
    while (m)
    {
        for (int i = 0; i < t; i++)
        {
            for (int j = 0; j < t; j++)
            {
                tmp[i][j] = ret[i][j];
            }
        }

        if (m & 1)
        {
            mul(ret, tmp, dp);
        }
        m = m >> 1;
        mul(tmp, dp, dp);
        for (int i = 0; i < t; i++)
        {
            for (int j = 0; j < t; j++)
            {
                dp[i][j] = tmp[i][j];
            }
        }
    }

    cout << ret[0][t - 1] << endl;

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FreeBuf

绿盟科技威胁分析报告:那些年,那些 Apache Struts2 的漏洞

每次 Apache Struts2 漏洞爆发都在互联网上掀起腥风血雨,我们整理了近年来 Apache Struts2 高风险漏洞的信息供大家参考。针对此次 Ap...

29210
来自专栏landv

华为交换机批量加入 Vlan 方法

4.3K2
来自专栏知识分享

5-学会刷Wi-Fi模块固件(刷LUA版本固件)

http://www.cnblogs.com/yangfengwu/p/9065559.html

913
来自专栏SAP最佳业务实践

SAP最佳业务实践:FI–现金管理(160)-24银企对账-供应商付款-承兑汇票-对账单再处理

4.7.4 FEBA_BANK_STATEMENT帐户对帐单的重新处理 ? 输入公司代码、开户行、账户标识 ? 清帐凭证没有生成,重新执行。 点击菜单 编辑-过...

3175
来自专栏Golang语言社区

完整的golang 多协程+信道 任务处理示例

有几个地方需要注意:for i + 协程时如果协程使用可 i ,那么需要增加 i:= 来防止多协程冲突;实际执行任务时需要用一个函数包起来,防止单个任务pani...

3237
来自专栏后台全栈之路

U-boot两个修改:ARP支持和UDP校验支持

本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。

1453
来自专栏Golang语言社区

完整的golang 多协程+信道 任务处理示例

有几个地方需要注意:for i + 协程时如果协程使用可 i ,那么需要增加 i:= 来防止多协程冲突;实际执行任务时需要用一个函数包起来,防止单个任务pani...

4845
来自专栏IT开发技术与工作效率

Excel公式发送邮件、打开本文件目录、链接指定位置——HyperLink公式妙用

4614
来自专栏张善友的专栏

使用反向代理发布内网服务

DMZ是英文“demilitarizedzone”的缩写,中文名称为“隔离区”,也称“非军事化区”。它是为了解决安装防火墙后外部网络不能访问内部网络服务器的问题...

2338
来自专栏Huramkin的归档库

在Telegram搭建一个订阅机器人

如何创建机器人自行搜索 这里我刚刚创建了个机器人@PushRss_Bot 获取到了Token 进入这个目录

8791

扫码关注云+社区

领取腾讯云代金券