大意

求长度为n的，满足

• 只有字符A，G，C，T
• 没有子串AGC
• 在单次操作（交换相邻两个字符）后仍然满足上述条件

的串的个数。

思路

考虑把第三个限制去掉。

不满足限制的字符串有：

• AGC ，违反第二条限制
• ACG ，交换C，G之后违反
• GAC ，交换G，A之后违反
• AGGC ，交换G，A之后违反
• AGTC ，交换T，C之后违反
• ATGC ，交换T，A之后违反

以及以它们为字串的字符串（这里不考虑违反第一条限制的字符串）。

我们使用 $5$ 进制。用 $0$ 表示 ，即没用字符；用 $1$ 表示A，用 $2$ 表示G，用 $3$ 表示C，用 $4$ 表示T，用长度为 $3$ 的五进制数表示三个连续字符。

令 $a = (\text{前面三个字符})_5 \times (10)_5 + (\text{当前选的字符})_5$ ，则如果：

$$a \begin{cases} \mod 125 & = & \begin{cases} 38 & (AGC) \\ 42 & (ACG) \\ 58 & (GAC) \end{cases} \\ & = & \begin{cases} 188 & (AGGC) \\ 198 & (AGTC) \\ 238 & (ATGC) \end{cases} \end{cases}$$

那么违反限制，不能选，否则都可以进行转移。

代码如下：

代码

#include<bits/stdc++.h>
#define mod 1000000007
int n,dp[123][1000],ans;
int main(){
	scanf("%d",&n),dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<125;j++){
			if(dp[i-1][j]){
				for(int k=j*5+1;k<=j*5+4;k++){
					if(!(k%125==38||k%125==42||k%125==58||k==188||k==198||k==238)){
						dp[i][k%125]=(dp[i][k%125]+dp[i-1][j])%mod;
                    }
                }
            }
        }
    }
	for(int i=0;i<125;i++) ans=(ans+dp[n][i])%mod;
	printf("%d",ans);
}