[结论 + DP] AtCoder ARC094F - Normalization

这种看上去一脸不可做的题就要想到,可能有很强的结论...

长度小于等于 \(3\) 的暴力手玩...

对于 \(|S|\ge 4\) ,串 \(S\) 能变到 \(T\) ,当且仅当满足:

  1. \(abc\) 记为 \(012\)\(Sum(S)=Sum(T)\)
  2. \(T\) 要至少有一对相邻位置相等,除非 \(S=T\)

归纳证明... 然后瞎 \(DP\) 就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200005,P=998244353;
char a[maxn];
int n,f[maxn][3][3][2],sum;

bool Allsame(){
for(int i=2;i<=n;i++) if(a[i]!=a[i-1]) return false;
return true;
}
bool NoAdjsame(){
for(int i=2;i<=n;i++) if(a[i]==a[i-1]) return false;
return true;
}
int main(){
freopen("arc094_d.in","r",stdin);
freopen("arc094_d.out","w",stdout);
scanf("%s",a+1); n=strlen(a+1);
if(Allsame()) return puts("1"), 0;
if(n<=3){
if(n==2) puts("2");
else{
if(a[1]!=a[2]&&a[1]!=a[3]&&a[2]!=a[3]) puts("3");
else if(a[1]==a[3]) puts("7");
else puts("6");
}
return 0;
}
for(int i=1;i<=n;i++) sum=(sum+a[i]-'a')%3;
for(int i=0;i<=2;i++) f[1][i][i][0]=1;
for(int i=1;i<=n-1;i++)
for(int j=0;j<=2;j++)
for(int k=0;k<=2;k++)
for(int t=0;t<=1;t++)
for(int l=0;l<=2;l++) (f[i+1][l][(k+l)%3][t|(j==l)]+=f[i][j][k][t])%=P;
printf("%d\n",((LL)f[n][0][sum][1]+f[n][1][sum][1]+f[n][2][sum][1]+NoAdjsame())%P);
return 0;
}