用vue开发的网站,网站建设安全规范,前几年做那些网站致富,商丘峰少seo题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/369/A 来源#xff1a;牛客网
题目描述
我明白。
作为这命运剧场永远的观众#xff0c;小D一直注视着这片星光璀璨的舞台#xff0c;舞台上#xff0c;少女们的身姿演绎出了一幕幕…题干
链接https://ac.nowcoder.com/acm/contest/369/A 来源牛客网
题目描述
我明白。
作为这命运剧场永远的观众小D一直注视着这片星光璀璨的舞台舞台上少女们的身姿演绎出了一幕幕动人的场景令人回味无穷。
有的时候小D也会自己写一些歌曲来加入Starlight的剧本使得剧本充满了新的生命力。
现在小D又要准备写乐谱了小D写谱的方式比较独特。他会先写出一个按照音符出现顺序排成的序列再进一步整合每次整合会选取相邻的三个作为三和弦。整合次数无限。
小D选取的音符形如D5 F6这种形式例如D5表示D大调sol这里不考虑升降音为了方便生成乐谱他将这些音符进一步转化了小D给C D E F G A B重新编号成了1 2 3 4 5 6 7之后新的音符编号生成方式应为(字母对应的标号-1)*7数字例如C7(1−1)×777C7(1−1)×777
但小D讨厌一些他所认为的不优美的和弦因此他并不希望自己的谱子里面有可能出现这样的三和弦也就说音符组成的序列里不应该存在他所讨厌的子段假如C5 F1 A2这三个音符凑成的和弦小D不喜欢那么序列里面就不能出现C5 F1 A2C5 A2 F1A2 C5 F1A2 F1 C5F1 A2 C5F1 C5 A2这六种子段。
现在小D正在推算有多少合法的序列答案对 10971097 取模。
星屑飘洒的舞台上可人绽放的爱之花请努力让大家星光闪耀吧
输入描述:
第一行为两个整数 n, q 表示序列的长度和有多少和弦小D不喜欢.
接下来 q 行每行三个整数 a, b, c 表示小D不想出现的和弦
输出描述:
一行一个整数表示答案
示例1
输入
复制
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
示例2
输入
复制
3 1
1 2 3
输出
复制
117643
说明 一共有6种不合法的序列
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
答案为493−6117643493−6117643
备注:
3≤n≤500,0≤q≤117649,1≤a,b,c≤49
解题报告 眼残党表示刚开始没有读题、、认为q117649 正好是49^3嘛肯定不会有重复然后就GG了、、2333.。。。
dp[i][j][k]表示前i个字符其中倒数第二个为j倒数第一个为k时可以组成的方案数。
对于状态的转移我们有两种解法对于dp[i]的转移我们先把源自dp[i-1]的都累加过来然后看看需要减去多少这时候枚举去重完的这tot组和弦对于每一组分成三个数都相同其中两个数相同三个数都不相同三种情况分别进行转移就行了。你如果都直接减6组的话那就有可能减多了样例1就过不了别问我怎么知道的吃完饭回来才想出来。
第二种解法也是十分简单的先用三维数组标记三位数是否出现过直接枚举后三个数[j][k][l]如果没出现过那就转移如果出现过就continue。
AC代码1
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
ll dp[505][55][55],dpp[MAX];
int a[MAX],b[MAX],c[MAX],qq[3];
const ll mod 1e9 7;
int tot;
setpairint,pairint,int ss;
int main()
{int n,q;cinnq;for(int x,y,z,i 1; iq; i) {scanf(%d%d%d,qq,qq1,qq2);sort(qq,qq3);xqq[0],yqq[1],zqq[2];if(ss.count(pm(x,pm(y,z)))) continue;else a[tot] x,b[tot]y,c[tot]z,ss.insert(pm(x,pm(y,z)));}for(int i 1; i2; i) {for(int j 1; j49; j) {for(int k 1; k49; k) {dp[i][j][k] 1;}}}for(int i 3; in; i) {for(int j 1; j49; j) {for(int k 1; k49; k) {for(int l 1; l49; l) {dp[i][j][k] dp[i-1][l][j];dp[i][j][k] % mod;}}}
// memset(dpp,0,sizeof dpp);
// //求出以i中间的dpp[i]
// for(int j 1; j49; j) {
// for(int k 1; k49; k) {
// dpp[j] dp[i-1][k][j];
// }
// }for(int e 1; etot; e) {int A a[e],B b[e],C c[e];int xx[3];xx[0]A,xx[1]B,xx[2]C;sort(xx,xx3);Axx[0],Bxx[1],Cxx[2];if(ABBC) dp[i][A][B] (dp[i][A][B]mod - dp[i-1][C][A])%mod;else if(AB B!C) {dp[i][A][B] (dp[i][A][B]mod - dp[i-1][C][A])%mod;dp[i][A][C] (dp[i][A][C]mod - dp[i-1][B][A])%mod;dp[i][C][A] (dp[i][C][A]mod - dp[i-1][B][C])%mod;}else if(A!B BC) {dp[i][A][B] (dp[i][A][B]mod - dp[i-1][C][A])%mod;dp[i][B][A] (dp[i][B][A]mod - dp[i-1][C][B])%mod;dp[i][B][C] (dp[i][B][C]mod - dp[i-1][A][B])%mod;}else {dp[i][A][B] (dp[i][A][B]mod - dp[i-1][C][A])%mod;dp[i][B][A] (dp[i][B][A]mod - dp[i-1][C][B])%mod;dp[i][A][C] (dp[i][A][C]mod - dp[i-1][B][A])%mod;dp[i][C][A] (dp[i][C][A]mod - dp[i-1][B][C])%mod;dp[i][B][C] (dp[i][B][C]mod - dp[i-1][A][B])%mod;dp[i][C][B] (dp[i][C][B]mod - dp[i-1][A][C])%mod;}}}ll ans 0;for(int j 1; j49; j) {for(int k 1; k49; k) {ans (ans dp[n][j][k])%mod; }}printf(%lld\n,ans);return 0 ;}
/*
4 1
1 2 3
3 1
1 1 2*/ AC代码2
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
ll dp[505][55][55],dpp[MAX];
bool bk[55][55][55];
const ll mod 1e9 7;
int main()
{int n,q;cinnq;for(int x,y,z,i 1; iq; i) {scanf(%d%d%d,x,y,z);bk[x][y][z]1; bk[x][z][y]1;bk[y][x][z]1; bk[y][z][x]1;bk[z][x][y]1; bk[z][y][x]1;}for(int i 1; i2; i) {for(int j 1; j49; j) {for(int k 1; k49; k) {dp[i][j][k] 1;}}}for(int i 3; in; i) {for(int j 1; j49; j) {for(int k 1; k49; k) {for(int l 1; l49; l) {if(bk[j][k][l]) continue ;dp[i][j][k] dp[i-1][l][j];dp[i][j][k] % mod;}}}}ll ans 0;for(int j 1; j49; j) {for(int k 1; k49; k) {ans (ans dp[n][j][k])%mod; }}printf(%lld\n,ans);return 0 ;}
/*
4 1
1 2 3
3 1
1 1 2*/
