题解：P14256 平局（draw）
s4CRIF1CbUbbL3AtIAly
·
·
题解
为什么没有人思考一个正常一点的 dp 啊（
其实也有可能是这个做法假了。如果确实假了记得踢我。
有一个唐人 dp 细节没想清楚就来写题解。最终的 dp 式子和其他题解是本质相同的，只是理解方式不太一样。
因为我不喜欢区分石头剪刀布，所以我直接忽略每个位置具体是什么，因为我们只关心相邻两个人谁能赢谁。
我们在任意相邻两个人之间画一个箭头，由胜者指向败者。如果两个人是平局就变成 =。不过一般来说可以先操作一次解决掉 =。
那么，分析一下当我们删除一个箭头的时候会发生什么。不妨假设我们删除了一个 \to，那么 \to\gets 会变成一个 =，然后消除掉 =。如果是 \to\to 则会变成一个 \gets。因此我们造出 = 只有如下几种办法：
- 自带的 =
- 将一个 \to\gets 变成 =
- 将一个 \to\to\to 或 \gets\gets\gets 变成 \to\gets 然后变成 =
那我们不妨给每个点添加一个高度，使得相邻两个人的高度只差 1，且胜者那边高度更高。（如果两个人类型相同就直接高度一样）
于是我们就能够得到一个折线图，这个折线图能够清晰的表示出 1 和 2 两种制造 = 的方式：两个箭头如果在同一层上而且中间所有箭头都更低就可以等到中间的箭头全都消完之后将这对 \to\gets 变成 =。
如上图，画的比较丑请见谅。图中所有横线就是我们的匹配方案。
于是我们不难猜测直接这样匹配的方式是不劣的：如果不这么做，我们就只能用上述的第三种方法，那这样的话我们会用四行来完成这一组匹配。如果对面的四行也如此，最多也就只能这样用四行获得两组匹配，显然远不如直接做。
于是我们就已经得出了答案。先缩掉所有 =，之后把除了所有前缀 \max 和后缀 \max 的部分全都两两匹配，最后剩一个倒过来的 V 字形。而对于这一部分我们就终于可以使用第三种方法匹配了。
对于一个连续 n 个 \to 组成的连续段，我们一直使用第三种方法可以获得 \lfloor\frac n3\rfloor 次 =。\gets 同理。
那么我们把答案的贡献分成三部分：初始状态的 =，两两匹配的部分，最后倒过来的那个 V 字形。
----
现在我们的核心问题就是第三部分。先只考虑倒 V 的前半部分大小。不难发现只要我们令第一个人的高度是 $0$，那么高度 $\max$ 就是前半部分的箭头个数。因为此处 $/3$ 需要下取整，所以尝试求出 $\max$ 为每一个数的方案数。
容易想到一个普通的三次方 DP：记 $f_{i,j,k}$ 表示考虑前 $i$ 个数，目前 $\max=j$，最后一位高度为 $k$ 的方案数。但是因为状态就是三次方的，难以优化。
既然从前往后不好考虑，那就换一个方向，从后往前加数。每次在当前串的第一位加入一个括号，这样 $\max$ 的变化就很简单了，于是我们只需要记当前从后往前加入到哪一位以及只考虑这个后缀的 $\max$ 是多少即可，转移显然为 $O(1)$，于是总复杂度 $O(n^2)$。注意因为相邻两位之间的箭头方向是由两侧取到哪个值决定的，所以其实 DP 里还需要记录一下当前第一位的人打算出什么。
后半部分和前半部分是对称的，只需要把输入的序列倒过来重新做一次即可。这样我们就能够简单计算上面提到的所有贡献了，于是整个题就在~~小常数的~~ $O(n^2)$ 复杂度内完成。
----
于是你高兴的写完代码，发现第三个样例过不去。贺一个 std 过来对拍一下，发现这个情况挂了：
```
5
12421
```
这是因为，其实我们可以把一个 $\gets\gets\to\to$ 用一次操作变成 $\gets\gets\gets$，这样本来两边高度 $\bmod 3$ 分别是 $2$ 和 $2$，现在用一次操作变成了 $0$ 和 $0$，并且使答案增加了 $1$。
这说明如果一个序列最终剩下的倒 V 两侧长度都 $\bmod 3=2$，答案需要增加 $1$。同时处理前后太困难了，发现这个等价于倒 V 前半部分长度 $\bmod 3=2$ 且折线首尾高度之差是 $3$ 的倍数。
于是我们直接在 dp 的时候再加上一维表示当前折线首尾高度差 $\bmod 3$，最后把这一部分的贡献加上即可。
于是就成功以一个超大常数的 $O(n^2)$ 通过了此题。
```cpp
int n;
int a[3005],C[15];
ll iv[5];
ll seq,cntp;
int ca(int x,int y){// x -> y
return x==y?0:x==(y+1)%3?-1:1;
}
ll ans;
ll cmx1,cmx2;
ll dp[3005][3005][3][3];// 四维含义见上
void solve(ll&cm,bool tp=0){
// cerr<<"solve\n";
Cl(dp);
for(int i=0;i<3;i++)if(a[n]>>i&1)dp[n][0][i][0]=1;
for(int i=n-1;i;i--)for(int j=0;j<=n-i;j++)for(int x=0;x<3;x++)
for(int h=0;h<3;h++)if(dp[i+1][j][x][h])for(int y=0;y<3;y++)if(a[i]>>y&1){
int v=ca(y,x);
(dp[i][max(j+v,0)][y][(h+v+3)%3]+=dp[i+1][j][x][h])%=mod;
}// 直接转移
for(int h=0;h<n;h++){
ll s=0;
for(int x=0;x<3;x++)for(int y=0;y<3;y++)(s+=dp[1][h][x][y])%=mod;
(ans+=(h/3)*s)%=mod;
(cm+=s*h)%=mod;
if(h%3==2&&tp)// 特殊计算的贡献
for(int x=0;x<3;x++)(ans+=dp[1][h][x][0])%=mod;
}
}
void __INIT__(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
void __SOLVE__(){
cin>>n;
cntp=1;
C[1]=C[2]=C[4]=1;
C[3]=C[5]=C[6]=2;
C[7]=3;
iv[1]=1;
iv[2]=mod+1>>1;
iv[3]=(mod+1)/3;
for(int i=1;i<=n;i++){
char c;
cin>>c;
a[i]=c-48;
(cntp*=C[a[i]])%=mod;
}
for(int i=1;i<n;i++)
(seq+=cntp*iv[C[a[i]]]%mod*iv[C[a[i+1]]]%mod*C[a[i]&a[i+1]])%=mod;
ans=seq;// 这个是 = 的贡献之和
solve(cmx1,1);
reverse(a+1,a+n+1);
solve(cmx2);// 直接倒过来跑一遍就是对的
ll mch=cntp*(n-1)%mod+mod-seq+mod-cmx1+mod-cmx2;// 两两匹配这一部分的贡献直接在这里拆开计算
mch=(mch%mod)*iv[2]%mod;
(ans+=mch)%=mod;
cout<<ans<<"\n";
}
```