洛谷题面

前言

洛谷第一篇题解。

我只希望 @liubinze 和 @Sham_Devour 能提前看到这篇题解...

题目描述

给定一个整数 \(N\)，请找出满足下列要求的长度为 \(N\) 的字符串的数目，答案对 \(10^9+7\) 取模。

• 该字符串仅由 A C G T 四种字符组成

• 该字符串不包含子串 AGC

• 交换相邻两个字符一次不违反上述要求

题目分析

因为我们必须满足『交换相邻两个字符一次不违反上述要求』这一条件，而上述要求即『该字符串不包含子串 AGC』，所以可以得到『字串必然不包括ACG,GAC,AGC,A?GC,AG?C』。

其中 ? 是 A C G T 中任一字符。

我们令 \(dp[i][a][b][c]\) 表示在长度为 \(i\) 的字符串中，最后三个字符为 \(a,b,c\) 且满足条件的字符串数量。

我们令 \(1\) 代表 A，\(2\) 代表 C,\(3\) 代表 G，\(4\) 代表 T。

那么我们在枚举的时候排除一下 ACG,GAC,AGC,A?GC,AG?C 的情况即可：

if(a==1 && b==2 && d==3)continue;
if(a==1 && c==2 && d==3)continue;
if(b==1 && c==2 && d==3)continue;
if(b==1 && c==3 && d==2)continue;
if(b==2 && c==1 && d==3)continue;

代码

//2021/9/11

#include <iostream>

#include <cstdio>

#define int long long 

#define debug(c) cerr<<#c<<" = "<<c<<endl

#define cek() puts("qwq")

namespace Newstd
{
	inline int read()
	{
		char c;
		bool flag=false;
		while((c=getchar())<'0' || c>'9')
		{
		    if(c=='-') flag=true;
		}
		int res=c-'0';
		while((c=getchar())>='0' && c<='9')
		{
		    res=(res<<3)+(res<<1)+c-'0';
		}
		return flag?-res:res;
	}
	inline void print(int x)
	{
		if(x<0)
		{
			putchar('-');x=-x;
		}
		if(x>9)
		{
			print(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int ma=105;

const int mod=1e9+7;

int dp[ma][5][5][5];

int n;

#undef int

int main(void)
{
	#define int long long
	
	scanf("%lld",&n);
	
	dp[0][0][0][0]=1ll;
	
	for(register int i=0;i<n;i++)
	{
		for(register int a=0;a<5;a++)
		{
			for(register int b=0;b<5;b++)
			{
				for(register int c=0;c<5;c++)
				{
					for(register int d=1;d<5;d++)
					{
						if(a==1 && b==2 && d==3)
						{
							continue;
						}
						
						if(a==1 && c==2 && d==3)
						{
							continue;
						}
						
						if(b==1 && c==2 && d==3)
						{
							continue;
						}
						
						if(b==1 && c==3 && d==2)
						{
							continue;
						}
						
						if(b==2 && c==1 && d==3)
						{
							continue;
						}
						
						dp[i+1][b][c][d]=(dp[i+1][b][c][d]+dp[i][a][b][c])%mod;
					}
				}
			}
		}
	}
	
	int ans(0);
	
	for(register int i=1;i<5;i++)
	{
		for(register int j=1;j<5;j++)
		{
			for(register int k=1;k<5;k++)
			{
				ans=(ans+dp[n][i][j][k])%mod;
			}
		}
	}
	
	printf("%lld\n",ans);
	
	return 0;
}