复杂动态规划

程序员文章站 2022-09-21 15:24:14

文章目录整数划分鸣人的影分身糖果密码脱落生命之树斐波那契前 n 项和包子凑数括号配对旅游规划垒骰子整数划分整数划分题目大意一个正整数 nnn 可以表示成若干个正整数之和，形如：n=n1+n2+…+nkn=n_1+n_2+…+n_kn=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1n_1≥n_2≥…≥n_k,k≥1n1≥n2≥…≥nk,k≥1。我们将这样的一种表示称为正整数n的一种划分。现在给定一个正整数 nnn，请你求出 nnn 共有多少种不同的划分方法。输入格式共一行...

文章目录

整数划分
鸣人的影分身
糖果
密码脱落
生命之树
斐波那契前 n 项和
包子凑数
括号配对
旅游规划
垒骰子

整数划分

整数划分
题目大意
一个正整数 $n$ 可以表示成若干个正整数之和，形如： $n=n_1+n_2+…+n_k$ ，其中 $n_1≥n_2≥…≥n_k,k≥1$ 。
我们将这样的一种表示称为正整数n的一种划分。
现在给定一个正整数 $n$ ，请你求出 $n$ 共有多少种不同的划分方法。
输入格式
共一行，包含一个整数 $n$ 。
输出格式
共一行，包含一个整数，表示总划分数量。
由于答案可能很大，输出结果请对 $10^9+7$ 取模。
数据范围： $1 \leq n \leq 1000$
输入样例

输出样例

$1 . 状态表示： d p [i] [j] 表示 j 个数凑出容量为 i 的方案数。$
$2 . 状态转移方程：最后一个数是大于 0 与最后一个数大于 0 的两种方案数之和。即 d p [i] [j] = d p [i] [j - 1] + d p [i - j] [j]$

#include <cstdio>
using namespace std;
const int mod=1e9+7;
int dp[1007][1007];  // dp[i][j]:前 j 个数,容量为 i 的方案数
int main()
{
    int n;
    scanf("%d",&n);
    
    for(int i = 0; i <= n; i++) dp[0][i] = 1;  // i 个数,全 0 方案数为 1
    for(int i = 0; i <= n; i++)  //容量为 i
        for(int j = 1; j <= n; j++)  // 个数为 j 个
        {
            dp[i][j] = dp[i][j-1]%mod;
            if(i >= j) dp[i][j] += dp[i-j][j]%mod;
        }
    printf("%d\n",dp[n][n]);
    return 0;
}

#include <cstdio>
using namespace std;
const int mod=1e9+7;
int dp[1007];
int main()
{
    int n;
    scanf("%d",&n);
    dp[0]=1;  //容量为 0 的方案数是 1

    for(int i=1;i<=n;++i)  //枚举物品
        for(int j=i;j<=n;++j)  //枚举容量
            dp[j]=(dp[j]+dp[j-i])%mod;

    printf("%d\n",dp[n]);
    return 0;
}

鸣人的影分身

鸣人的影分身
题目大意
在火影忍者的世界里，令敌人捉摸不透是非常关键的。
我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。
针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。
那么问题来了，假设鸣人的查克拉能量为 $M$ ，他影分身的个数最多为 $N$ ，那么制造影分身时有多少种不同的分配方法？
注意：影分身可以分配0点能量。
分配方案不考虑顺序，例如： $M = 7, N = 3$ ，那么 (2,2,3) 和 (2,3,2) 被视为同一种方案。
输入格式
第一行是测试数据的数目 $t$ 。
以下每行均包含二个整数 $M$ 和 $N$ ，以空格分开。
输出格式
对输入的每组数据 $M$ 和 $N$ ，用一行输出分配的方法数。
数据范围： $0 \leq t \leq 20, 1 \leq M, N \leq 10$
输入样例

1
7 3

输出样例

1.确定状态： $d p [i] [j]$ 表示 $j$ 个数，和为 $i$ 的方案数。
2.状态转移方程：最后一位是 0 表示为 $d p [i] [j - 1]$ ，最后一位大于 0 表示为 $d p [i - j] [j]$

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 20;
int dp[maxn][maxn];
int main()
{
    int n, m, t;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp, 0, sizeof dp);
        scanf("%d%d",&m,&n);
        dp[0][0] = 1;
        for(int i = 0; i <= m; i++)
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = dp[i][j-1];  //最后一个数是 0
                if(i >= j) dp[i][j] += dp[i-j][j];  // 最后一个数大于 0
            }
        printf("%d\n",dp[m][n]);
    }
    return 0;
}

糖果

糖果
题目大意
由于在维护世界和平的事务中做出巨大贡献， $D z x$ 被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。
在这一天， $D z x$ 可以从糖果公司的 $N$ 件产品中任意选择若干件带回家享用。
糖果公司的 $N$ 件产品每件都包含数量不同的糖果。
$D z x$ 希望他选择的产品包含的糖果总数是 $K$ 的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。
当然，在满足这一条件的基础上，糖果总数越多越好。
$D z x$ 最多能带走多少糖果呢？
注意： $D z x$ 只能将糖果公司的产品整件带走。
输入格式
第一行包含两个整数 $N$ 和 $K$ 。
以下 $N$ 行每行 1 个整数，表示糖果公司该件产品中包含的糖果数目，不超过 1000000。
输出格式
符合要求的最多能达到的糖果总数，如果不能达到 $K$ 的倍数这一要求，输出 0。
数据范围： $1 \leq N \leq 100, 1 \leq K \leq 100$
输入样例

输出样例

样例解释： $D z x$ 的选择是2+3+4+5=14，这样糖果总数是7的倍数，并且是总数最多的选择。
$1 . 状态表示： d p [i] [j] 在 i 个数中选，取模 k 余数是 j 的方案数。$
$2 . 状态转移：不选第 i 个数， d p [i - 1] [j], 选第 i 个数 d p [i - 1] [(j + k - w$ % $k)$ % $k]$

#include <cstdio>
#include <cstring>
using namespace std;
int dp[110][110]; // dp[i][j]:前 i 个数中选,且%k余数是j的方案数
int max(int x,int y)
{
    return x > y ? x : y;
}
int main()
{
    int n, k, w;
    scanf("%d%d",&n,&k);
    memset(dp, -0x3f, sizeof dp);
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d",&w);  
        for(int j = 0; j < k; j++)
            dp[i][j] = max(dp[i-1][j],dp[i-1][(j+k-w%k)%k]+w);
    }
    printf("%d\n",dp[n][0]);
    return 0;
}

密码脱落

密码脱落
题目大意
$X$ 星球的考古学家发现了一批古代留下来的密码。
这些密码是由 $A 、 B 、 C 、 D$ 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入格式
共一行，包含一个由大写字母 $A B C D$ 构成的字符串，表示现在看到的密码串。
输出格式
输出一个整数，表示至少脱落了多少个种子。
数据范围：输入字符串长度不超过1000
输入样例

ABCBA
ABDCDCBABC

输出样例

0
3

1.确定状态： $d p [l] [r]$ 表示字符串从左边到右边的最长回文子串，值代表子串的长度。
2.状态转移方程：左边界的字符与有边界的字符匹配，回文子序列长度 + 2，左边右移一位，右边左移一位，不匹配时取只包含左边界或者只包含右边界的最大值。(这是我的个人理解，可能描述比较模糊，望海涵)

#include <cstdio>
#include <cstring>
using namespace std;
char s[1007];
int dp[1007][1007];  //从左边界 -> 右边界 最长回文子序列
int max(int x, int y)
{
    return x > y ? x : y;
}
int main()
{
    scanf("%s",s);
    int len = strlen(s);
    for(int i = 1; i <= len; i++)
    {
        for(int l = 0; l + i - 1 < len; l++)
        {
            int r = l + i - 1;
            if(i == 1) dp[l][r] = 1;
            else
            {
                if(s[l] == s[r]) dp[l][r] = dp[l+1][r-1] + 2;
                dp[l][r] = max(dp[l][r],dp[l+1][r]);
                dp[l][r] = max(dp[l][r],dp[l][r-1]);
            }
        }
    }
    int ans = len - dp[0][len-1];
    printf("%d\n",ans);
    return 0;
}

生命之树

生命之树
题目大意
在 $X$ 森林里，上帝创建了生命之树。
他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。
上帝要在这棵树内选出一个非空节点集 $S$ ，使得对于 $S$ 中的任意两个点 $a, b$ ，都存在一个点列 { $a,v_1,v_2,…,vk,b$ } 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。
在这个前提下，上帝要使得 $S$ 中的点所对应的整数的和尽量大。
这个最大的和就是上帝给生命之树的评分。
经过 $a t m$ 的努力，他已经知道了上帝给每棵树上每个节点上的整数。
但是由于 $a t m$ 不擅长计算，他不知道怎样有效的求评分。
他需要你为他写一个程序来计算一棵树的分数。
输入格式
第一行一个整数 $n$ 表示这棵树有 $n$ 个节点。
第二行 $n$ 个整数，依次表示每个节点的评分。
接下来 $n - 1$ 行，每行 2 个整数 $u, v$ ，表示存在一条 $u 到 v$ 的边。
由于这是一棵树，所以是不存在环的。
树的节点编号从 1 到 $n$ 。
输出格式
输出一行一个数，表示上帝给这棵树的分数。
数据范围： $1≤n≤10^5$
每个节点的评分的绝对值均不超过 $10^6$ 。
输入样例

5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

输出样例

#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
struct node
{
    int to, ne;  //to:到达边, ne:后继指针
};
node edge[maxn<<1];  //无项边
int tot = 0, head[maxn<<1];
ll f[maxn], a[maxn];
void add(int x, int y)  //存储边
{
    edge[++tot].to = y;
    edge[tot].ne = head[x];
    head[x] = tot;
}

ll max(ll x, ll y)  //比较函数
{
    return x > y ? x : y;
}

void dfs(int now, int fa)
{
    f[now] = a[now];  //当前节点的权值
    for(int i = head[now]; i; i = edge[i].ne)  //搜索子树
    {
        int to = edge[i].to;  //当前节点 -> 下一个节点
        if(to != fa)  //到达的节点是否等于父节点
        {
            dfs(to, now);  //继续递归搜索
            f[now] += max(f[to],0ll);  //树上求最大值
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%lld",&a[i]);
    for(int i = 1; i < n; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);  //加边 x -> y
        add(y,x);  //加边 y -> x
    }
    dfs(1,0);  //从 1 号节点开始搜
    ll ans = f[1];
    for(int i = 2; i <= n; i++) ans = max(ans,f[i]);
    printf("%lld\n",ans);
    return 0;
}

斐波那契前 n 项和

斐波那契前 n 项和
题目大意
大家都知道 $F i b o n a c c i$ 数列吧， $f_1=1,f_2=1,f_3=2,f_4=3,…,f_n=f_{n−1}+f_{n−2}$ 。
现在问题很简单，输入 $n$ 和 $m$ ，求 $f_n$ 的前 $n$ 项和 $S n m o d m$ 。
输入格式
共一行，包含两个整数 $n$ 和 $m$ 。
输出格式
输出前 $n$ 项和 $S n m o d m$ 的值。

数据范围： $1 \leq n \leq 2000000000, 1 \leq m \leq 1000000010$
输入样例

5 1000

输出样例

参考文献
 本蒟蒻博客
$\left ( \begin{matrix} A & 1 \\ B & 0 \end{matrix} \right )^{n-2}$
这里的 $A$ 和 $B$ 都是1
结论：观察原式 $f_n=f_{n−1}+f_{n−2}$
移项可得 $f_{n−2}=f_n−f_{n−1}$
也就是 $f_n=f_{n+2}−f_{n+1}$
将斐波那契的前n项都写成这种形式，得
$f_1= f_3−f_2$
$f_2= f_4−f_3$
$f_3= f_5−f_4$
$f_4= f_6−f_5$
⋮
$f_n= f_{n+2}−f_{n+1}$
累加所有等式，
左边正好是我们要求的答案
而右边，从f1到fn+1，都互相抵消掉了，
得到
$f_1+f_2+⋯+f_n=f_{n+2}−f_2=f_{n+2}−1$
也就是说，我们就只需要求出 $f_{n+2−1}$ 即可
结论摘自&&二元组的解法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,mod;
struct Matrix{
    ll m[2][2];
};
Matrix MatrixMultiply(Matrix a, Matrix b)  
{ 矩阵乘法：矩阵A第i行所有数分别乘以矩阵B第j列对应的数 = ans[i][j]的值
    Matrix ans;
    ans.m[0][0] = ans.m[0][1] = ans.m[1][0] = ans.m[1][1] = 0;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++) 
                ans.m[i][j] =(ans.m[i][j]+(a.m[i][k]*b.m[k][j])%mod)%mod;
    return ans;
};
ll ksm(int b, int A, int B)  // f(n) = (A∗f(n−1)+B∗f(n−2))%mod
{
    struct Matrix ans, a;
    ans.m[0][0] = ans.m[1][1] = 1;   //  1  0
    ans.m[0][1] = ans.m[1][0] = 0;   //  0  1
    a.m[0][0] = A; a.m[0][1] = 1;   //   A  1
    a.m[1][0] = B; a.m[1][1] = 0;   //   B  0
    while(b)  //类似快速幂思想
    {
        if(b&1) ans = MatrixMultiply(ans,a);
        a = MatrixMultiply(a,a);
        b >>= 1;
    }
    return (ans.m[0][0] + ans.m[1][0])%mod;
}
int main()
{
    while(~scanf("%d%d",&n,&mod))
    {
        if(n == 1)
        {
            printf("%d\n",1%mod);
        }
        else if(n == 2)
        {
            printf("%d\n",2%mod);
        }
        else printf("%lld\n",ksm(n,1,1)-1);
    }
    return 0;
}

包子凑数

包子凑数
题目大意
小明几乎每天早晨都会在一家包子铺吃早餐。
他发现这家包子铺有 $N$ 种蒸笼，其中第 $i$ 种蒸笼恰好能放 $A_i$ 个包子。
每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买 $X$ 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 $X$ 个包子。
比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。
当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。
比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。
而顾客想买 7 个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入格式
第一行包含一个整数 $N$ 。
接下来 $N$ 行，每行包含一个整数 $A_i$ 。
输出格式
输出一个整数代表答案。
如果凑不出的数目有无限多个，输出 $I N F$ 。
数据范围： $1≤N≤100,1≤A_i≤100$
输入样例1

2
4
5

输出样例1

输入样例2

2
4
6

输出样例2

INF

样例解释
对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
对于样例2，所有奇数都凑不出来，所以有无限多个。

#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 7;
ll a[110], f[110][maxn];
ll gcd(ll x, ll y)
{
    return y == 0 ? x : gcd(y,x%y);
}
int main()
{
    int n, d = 0;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]), d = gcd(d,a[i]);
    if(d == 1)
    {
        f[0][0] = 1;  
        for(int i = 1; i <= n; i++)   //前 i 个物品
            for(int j = 0; j < maxn; j++)  //总和是 j
            {
                f[i][j] = f[i-1][j];
                if(j >= a[i]) f[i][j] |= f[i][j-a[i]];
            }
        int ans = 0;
        for(int i = 1; i < maxn; i++)
            if(!f[n][i]) ans++;
        printf("%d\n",ans);
    }
    else puts("INF");
    return 0;
}

空间优化

#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 7;
ll a[110], f[maxn];
ll gcd(ll x, ll y)
{
    return y == 0 ? x : gcd(y,x%y);
}
int main()
{
    int n, d = 0;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]), d = gcd(d,a[i]);
    if(d == 1)
    {
        f[0] = 1;  
        for(int i = 1; i <= n; i++)   //前 i 个物品
            for(int j = a[i]; j < maxn; j++)  //总和是 j
                f[j] |= f[j-a[i]];
        int ans = 0;
        for(int i = 1; i < maxn; i++)
            if(!f[i]) ans++;
        printf("%d\n",ans);
    }
    else puts("INF");
    return 0;
}

括号配对

括号配对
题目大意
$H e c y$ 又接了个新任务： $B E$ 处理。
$B E$ 中有一类被称为 $G B E$ 。
以下是 $G B E$ 的定义：
空表达式是 $G B E$
如果表达式 $A$ 是 $G B E$ ，则 $[A]$ 与 $(A)$ 都是 $G B E$
如果 $A$ 与 $B$ 都是 $G B E$ ，那么 $A B$ 是 $G B E$
下面给出一个 $B E$ ，求至少添加多少字符能使这个 $B E$ 成为 $G B E$ 。
注意： $B E$ 是一个仅由(、)、[、]四种字符中的若干种构成的字符串。
输入格式
输入仅一行，为字符串 $B E$ 。
输出格式
输出仅一个整数，表示增加的最少字符数。
数据范围：对于所有输入字符串，其长度小于100。
输入样例

[])

输出样例

/***
状态表示：dp[l][r]表示区间 l --> r的回文子序列集合
权值表示区间最长回文子序列
状态转移：当左端点和右端点匹配时: dp[l][r] = max(dp[l][r],dp[l+1][r-1]+2)
不匹配时：dp[l][r] = max(dp[l][r],dp[l][k]+dp[k+1][r]) (0 < k < r)
***/
#include <cstdio>
#include <cstring>
using namespace std;
int dp[110][110];
char s[110];
int max(int x, int y)
{
    return x > y ? x : y;
}
bool match(int l, int r)
{
    if(s[l] == '(' && s[r] == ')') return true;
    if(s[l] == '[' && s[r] == ']') return true;
    return false;
}
int main()
{
    memset(dp, 0, sizeof dp);  //初始化为 0 
    scanf("%s",s);
    int len = strlen(s);
    for(int i = 1; i <= len; i++)  //匹配次数
    {
        for(int l = 0; l + i - 1 < len; l++)  //左端点
        {
            int r = l + i - 1;  //右端点
            if(match(l,r)) //端点匹配
                dp[l][r] = max(dp[l][r], dp[l+1][r-1] + 2);
            for(int k = l; k < r; k++)  //寻找区间的最长回文子序列
                dp[l][r] = max(dp[l][r],dp[l][k]+dp[k+1][r]);
        }
    }
    printf("%d\n",len - dp[0][len-1]);
    return 0;
}

旅游规划

旅游规划
题目大意
$W$ 市的交通规划出现了重大问题，市*下定决心在全市各大交通路口安排疏导员来疏导密集的车流。
但由于人员不足， $W$ 市市长决定只在最需要安排人员的路口安排人员。
具体来说， $W$ 市的交通网络十分简单，由 $n$ 个交叉路口和 $n - 1$ 条街道构成，交叉路口路口编号依次为 $0, 1, \dots, n - 1$ 。
任意一条街道连接两个交叉路口，且任意两个交叉路口间都存在一条路径互相连接。
经过长期调查，结果显示，如果一个交叉路口位于 $W$ 市交通网最长路径上，那么这个路口必定拥挤不堪。
所谓最长路径，定义为某条路径 $p=(v_1,v_2,…,v_k)$ ，路径经过的路口各不相同，且城市中不存在长度大于 $k$ 的路径（因此最长路径可能不唯一）。
因此 $W$ 市市长想知道哪些路口位于城市交通网的最长路径上。
输入格式
第一行包含一个整数 $n$ 。
之后 $n - 1$ 行每行两个整数 $u, v$ ，表示编号为 $u$ 和 $v$ 的路口间存在着一条街道。
输出格式
输出包括若干行，每行包括一个整数——某个位于最长路径上的路口编号。
为了确保解唯一，请将所有最长路径上的路口编号按编号顺序由小到大依次输出。
数据范围： $1≤n≤2×10^5$
输入样例

输出样例

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 4e5 + 7;
const int maxm = 2e5 + 7;
struct node{
    int to,ne;
};
node edge[maxn];
int tot, head[maxm];
// d1[] 记录往下搜的最大长度, d2[] 记录往下搜的次大长度
int d1[maxm], d2[maxm], dw[maxm], up[maxm], maxd;
void add(int x, int y)
{
    edge[++tot].to = y;
    edge[tot].ne = head[x];
    head[x] = tot;
}
void dfs_d(int now, int fa) //往下搜
{
    for(int i = head[now]; i; i = edge[i].ne)
    {
        int to = edge[i].to;
        if(to != fa)  //防止往回搜
        {
            dfs_d(to, now);
            int dis = d1[to] + 1;
            if(dis > d1[now])  //大于最大值
            {
                d2[now] = d1[now], d1[now] = dis;
                dw[now] = to;
            }
            else if(dis > d2[now]) d2[now] = dis;  //次大值更新
        }
    }
    maxd = max(maxd, d1[now] + d2[now]);
}
void dfs_up(int now, int fa)  //往上搜
{
    for(int i = head[now]; i; i = edge[i].ne)
    {
        int to = edge[i].to;
        if(to != fa)  //防止往回搜
        {
            up[to] = up[now] + 1;  
            if(dw[now] == to) up[to] = max(up[to],d2[now] + 1);  //次大值更新
            else up[to] = max(up[to], d1[now] + 1);  //最大值更新
            dfs_up(to, now);
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i < n; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }    
    dfs_d(1, -1);
    dfs_up(1, -1);
    for(int i = 0; i < n; i++)
    {
        int d[3] = {d1[i], d2[i], up[i]};
        sort(d, d + 3);
        if(d[1] + d[2] == maxd) printf("%d\n",i);
    }
    return 0;
}

垒骰子

垒骰子
题目大意
赌圣 $a t m$ 晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。
经过长期观察， $a t m$ 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！
我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。
假设有 $m$ 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。
$a t m$ 想计算一下有多少种不同的可能的垒骰子方式。
两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
由于方案数可能过多，请输出模 $0^9+7$ 的结果。
输入格式
第一行包含两个整数 $n, m$ ，分别表示骰子的数目和排斥的组数。
接下来 $m$ 行，每行两个整数 $a, b$ ，表示 $a$ 和 $b$ 数字不能紧贴在一起。
输出格式
共一个数，表示答案模 $10^9+7$ 的结果。
数据范围： $1≤n≤10^9,1≤m≤36,1≤a,b≤6$
输入样例

2 1
1 2

输出样例

/***
f[i][j]表示考虑前i个骰子，且第i个骰子上面是点数j时的方案数。
f[i][j] = f[i-1][1] + f[i-1][2] +f[i-1][3] + f[i-1][4] + f[i-1][5] + f[i-1][6]
A^(n - 1)*[4 4 4 4 4 4] = [f[n][1] f[n][2] f[n][3] f[n][4] f[n][5] f[n][6]];（列向量）
***/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
const int mod = 1e9 + 7, N = 7;
using namespace std;
typedef long long ll;

struct Matrix{
  ll m[N][N];
};

int Turn(int x)  // 转换函数
{
    if(x > 3) return x - 3;
    return x + 3;
}

Matrix mul(Matrix a, Matrix b) //矩阵乘法
{
    Matrix ans;
    for(int i = 1; i < N; i++)
        for(int j = 1; j < N; j++) ans.m[i][j] = 0;

    for(int i = 1; i < N; i++)
        for(int j = 1; j < N; j++)
            for(int k = 1; k < N; k++)
                ans.m[i][j] = (ans.m[i][j] + (a.m[i][k]*b.m[k][j])%mod)%mod;
    return ans;
}

ll ksm(int b,Matrix a)
{
    Matrix ans;
    for(int i = 1; i < N; i++) 
    {
        for(int j = 1; j < N; j++)
            if(!(i-1)) ans.m[i][j] = 4;   // m[1]
            else ans.m[i][j] = 0;
    }
    while(b)  //类似快速幂
    {
        if(b&1) ans = mul(ans,a);  //ans = ans*a;
        a = mul(a,a);   // a = a*a;
        b >>= 1;
    }
    ll res = 0;
    for(int i = 1; i < N; i++) res = (res + ans.m[1][i]%mod)%mod;
    return res;
}

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

    Matrix a;
    for(int i = 1; i < N; i++)
        for(int j = 1; j < N; j++) a.m[i][j] = 4;
    while(m--)
    {
        int x, y;
        scanf("%d%d",&x,&y);
        a.m[x][Turn(y)] = 0;
        a.m[y][Turn(x)] = 0;
    }
    
    ll ans = ksm(n - 1,a);
    printf("%lld\n",ans);
    return 0;
}

本文地址：https://blog.csdn.net/Edviv/article/details/108856476

相关标签：蓝桥杯动态规划 Dp题解

上一篇： mysql超详细图文安装配置教程

下一篇： NVIDIA喜加一：《战地风云2042》免费送需RTX 3070及以上

复杂动态规划

文章目录

整数划分

鸣人的影分身

糖果

密码脱落

生命之树

斐波那契前 n 项和

包子凑数

括号配对

旅游规划

垒骰子

飞信打开错误处理之动态链接库USER32.dll错误解决方法

Android编程实现输入框动态自动提示功能

vue实现微信分享链接添加动态参数的方法

Java注解实现动态数据源切换的实例代码

动态给表添加删除字段并同时修改它的插入更新存储过程

动态SQL中返回数值的实现代码

sqlserver 动态创建临时表的语句分享

sp_executesql 使用复杂的Unicode 表达式错误的解决方法

Spring中如何动态注入Bean实例教程

HTML5在canvas中绘制复杂形状附效果截图