小D的剧场

若你摘得小的星星你将得到小的幸福

若你摘得大的星星你将得到大的财富

若两者都能摘得你将得到永远的愿望

摘星是罪孽的宽恕摘星是夜晚的奇迹

抓住它吧你所期望的那颗星

无法触及，因而耀眼

明明触及了，却还是耀眼

——《少女☆歌剧 Revue·Starlight》

题目描述

"我明白。"

作为这命运剧场永远的观众，小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)\times7+7=7$

但小D讨厌一些他所认为的不优美的和弦，因此他并不希望自己的谱子里面有可能出现这样的三和弦，也就说音符组成的序列里不应该存在他所讨厌的子段，假如C5 F1 A2这三个音符凑成的和弦小D不喜欢，那么序列里面就不能出现C5 F1 A2，C5 A2 F1，A2 C5 F1，A2 F1 C5，F1 A2 C5，F1 C5 A2这六种子段。

现在小D正在推算有多少合法的序列，答案对

取模。

星屑飘洒的舞台上，可人绽放的爱之花，请努力让大家星光闪耀吧！

#include<stdio.h> #define fo(i,a,b) for(int i=a;i<=b;i++) int n,q,aa,bb,cc; const int p=1e9+7; bool v[100][100][100]; long long f[1020][100][100],ans; int main(){ scanf("%d%d",&n,&q); while (q--){ scanf("%d%d%d",&aa,&bb,&cc); v[aa][bb][cc]=1; v[aa][cc][bb]=1; v[bb][aa][cc]=1; v[bb][cc][aa]=1; v[cc][aa][bb]=1; v[cc][bb][aa]=1; } fo(a,1,49) fo(b,1,49) f[2][a][b]=1; fo(i,3,n) fo(a,1,49) fo(b,1,49) fo(c,1,49) if (!v[a][b][c]){ f[i][b][c]+=f[i-1][a][b]; if (f[i][b][c]>=p) f[i][b][c]-=p; } fo(a,1,49) fo(b,1,49) ans+=f[n][a][b]; ans%=p; printf("%lld\n",ans); return 0; }

#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; long long DP[505][55][55]; bool V[55][55][55]={0}; int main() { int i,j,k,l,n,q; scanf("%d%d",&n,&q); while(q--) { scanf("%d%d%d",&i,&j,&k); V[i][j][k]=V[i][k][j]=V[j][i][k]=V[j][k][i]=V[k][i][j]=V[k][j][i]=1; } for(j=1;j<=49;j++) for(k=1;k<=49;k++)DP[2][j][k]=1; for(i=3;i<=n;i++) for(j=1;j<=49;j++) for(k=1;k<=49;k++) for(l=1;l<=49;l++) if(!V[j][k][l])DP[i][k][l]=(DP[i][k][l]+DP[i-1][j][k])%mod; for(k=0,i=1;i<=49;i++) for(j=1;j<=49;j++)k=(k+DP[n][i][j])%mod; printf("%d\n",k); return 0; }

详情