自动搬运

查看原文

来自洛谷，原作者为

	pmt2018 这个人很懒，但还是留下了一点东西

搬运于2025-08-24 22:27:05，当前版本为作者最后更新于2020-12-25 22:54:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Observation: 注意到一个非常重要的事实,由于我们是将所有连续相同字符之间的位置切开,因而对于一个串,它对应的结果串是唯一的。所以对于结果串而言,一种合法划分即对应一种合法初始串。

那么什么样的串是合法串呢？显然的有两个条件：

1. 每一段划分中间不能有连续相同字符，不然我们一定会在那个位置将其割开。
2. 对于划分中的连续两个子串$s,t$，$s$的首字符必须等于$t$的末字符，不然我们也不会去割那个位置。

不难证明这是一个充分必要条件。

由此可以得到一个朴素的DP想法，考虑$dp[i][ch]$表示已经把前i个字符割好了，且最后一个子串的首字母为ch，转移时从大往小枚举前一个划分位置$j$，判断$s[j+1\ldots i]$有无连续相同字符即可。这个东西的复杂度是$\Theta(n^2)$的，无法接受。

考虑优化。在这种划分问题中，有一个套路是考虑i时要么加入前一个划分，要么另起一段。这道题中也是同样的道理。令$dp[i][a][b][c]$表示最后一段最后一个字母为a，首字母为b，倒数第二段为c。

这样，对于$s[i+1]$来说，若$s[i+1]!=a$，那么自然可以添加进最后一段。若$a=c$，那么最后一段就可以结束，让$s[i+1]$自成一段。

这样复杂度即为$\Theta(n)$，转移时有一个$|\Sigma|^4$级别的常数，此题$|\Sigma|$为4，所以没有问题。

Code

#include<bits/stdc++.h>

#define y0 pmtx
#define y1 pmtxx
#define x0 pmtxxx
#define x1 pmtxxxx
#define pb push_back
#define mp make_pair
#define fi first 
#define se second
#define DEBUG printf("Passing Line %d in function [%s].\n",__LINE__,__FUNCTION__)

using namespace std;

typedef pair<int ,int > pii;
typedef vector<int > vi;
typedef long long ll;
typedef unsigned long long ull;

namespace FastIO{
    const int SIZE=(1<<20);
    char in[SIZE],*inS=in,*inT=in+SIZE;
    inline char Getchar(){
        if(inS==inT){inT=(inS=in)+fread(in,1,SIZE,stdin);if(inS==inT)return EOF;}
        return *inS++;
    }
    char out[SIZE],*outS=out,*outT=out+SIZE;
    inline void Flush(){fwrite(out,1,outS-out,stdout);outS=out;}
    inline void Putchar(char c){*outS++=c;if(outS==outT)Flush();}
    struct NTR{~NTR(){Flush();}}ztr;
}

#ifndef LOCAL
    #define getchar FastIO::Getchar
    #define putchar FastIO::Putchar 
#endif

template<typename T> inline void read(T &x){
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    x*=f;
}

template<typename T>inline void write(T x){
    if(!x)putchar('0');
    if(x<0)x=-x,putchar('-');
    static int sta[40];int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
const int maxn=200007,INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ll LINF=0x3f3f3f3f3f3f3f3fll;
const ll P=19260817;

template<typename T>inline void ckmax(T &x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T &x,T y){x=(y<x?y:x);}
template<typename T>inline T my_abs(T x){if(x<0)x=-x;return x;}
inline int mod1(int x){return x<MOD?x:x-MOD;}
inline int mod2(int x){return x<0?x+MOD:x;}
inline void add(int &x,int y){x=mod1(x+y);}
inline void sub(int &x,int y){x=mod2(x-y);}

char s[maxn];
int n;
int dp[maxn][4][4][4];
const char to[]="AGCT";
int ans=0;
int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(s[1]=='?'||s[1]==to[j])dp[1][j][j][i]=1;
		}
	}
	for(int i=2;i<=n;i++){
		for(int a=0;a<4;a++){
			if(s[i]!='?'&&s[i]!=to[a])continue;
			for(int b=0;b<4;b++){
				for(int c=0;c<4;c++){
					for(int la=0;la<4;la++){
						if(la!=a)add(dp[i][a][b][c],dp[i-1][la][b][c]);
						if(la==c)add(dp[i][a][a][b],dp[i-1][la][b][c]);
					}
				}
			}
		}
	}
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			add(ans,dp[n][i][j][i]);
		}
	}
	printf("%d",ans);
    return 0;
}

//things to remember
//1.long long
//2.array length
//3.freopen
//4 boarder case

update on 2021.2.3:

鉴于评论区有很多人(确信)询问$n^2$的做法，我这里简单的描述一下，转移大概就是

$$dp[i][a]=\sum_{j< i,s[i]=b,s[j+1]=a} dp[j][b](\forall k\in [j+1,i),s[k]!=s[k+1]) $$

转移时从大往小枚举k即可。