链接：https://ac.nowcoder.com/acm/contest/369/A
——《少女☆歌剧 Revue·Starlight》
题目描述
第一行为两个整数 n, q ，表示序列的长度和有多少和弦小D不喜欢.
接下来 q 行，每行三个整数 a, b, c ，表示小D不想出现的和弦
一行一个整数，表示答案
10 10 18 3 3 43 28 22 42 28 3 48 48 4 29 9 31 47 9 22 1 22 49 15 48 29 2 8 27 4 24 34
382785822
题意：给你一个序列长度n，现在每一个位置都有49种方案可以填入，再给出q种不合法的方案 问有多少种可行方案
结果对1e9+7取模
思路： dp[i][k][l] 表示第i各位置放置 k和l两种音符 我们只需要枚举49^3种情况 对于 j k l 可行的情况 我们就有递推式
dp[i][k][l]+=dp[i-1][j][k]
其实这么看来问题就没那么复杂了
#include <cstdio> #include <map> #include <iostream> #include<cstring> #include<bits/stdc++.h> #define ll long long int #define M 6 using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const ll mod=1e9+7; int n,q; ll dp[507][57][57]; //dp[i][k][l] 表示第i各位置放置 k和l两种音符 int a[50][50][50]; int main(){ ios::sync_with_stdio(false); while(cin>>n>>q){ memset(a,0,sizeof(a)); for(int i=1;i<=q;i++){ int ta,tb,tc; cin>>ta>>tb>>tc; a[ta][tb][tc]=1; a[ta][tc][tb]=1; a[tb][ta][tc]=1; a[tb][tc][ta]=1; //对不可行方案进行标记 a[tc][ta][tb]=1; a[tc][tb][ta]=1; } for(int i=1;i<=2;i++) for(int j=1;j<=49;j++) for(int k=1;k<=49;k++) //初始化 dp[i][j][k]=1; for(int i=3;i<=n;i++) for(int j=1;j<=49;j++) for(int k=1;k<=49;k++) for(int l=1;l<=49;l++){ if(a[j][k][l]) continue; dp[i][k][l]=(dp[i][k][l]+dp[i-1][j][k])%mod; //如果是可行方案则 jk的后面就可以是l } ll ans=0; for(int i=1;i<=49;i++) for(int j=1;j<=49;j++){ ans=(ans+dp[n][i][j])%mod; } cout<<ans<<endl; } }
原文：https://www.cnblogs.com/wmj6/p/10386359.html