专栏文章

P8194

xxujindong_
P8194题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mingb4el
此快照首次捕获于
2025/12/02 01:56
3 个月前
此快照最后确认于
2025/12/02 01:56
3 个月前
查看原文
爆标做法。考虑把 DP 套 DP 直接扔掉，钦定当前状态按后 1/2/41/2/4 个分段，强行分讨去掉重复情况：
最后一个分段，fi←fi+fi−1f_i\gets f_i+f_{i-1}；
若 [i−1,i][i-1,i] 相邻，最后两个分段，要求这两个交换，否则被两个 11 段替代，fi←fi+fi−2f_i\gets f_i+f_{i-2}。
若 [i−3,i][i-3,i] 是正方形，最后四个分段，先让 fi←fi+24fi−4f_i\gets f_i+24f_{i-4}，然后扣掉可以被替代的方案。
被 ii 分一段的某个方案替代：
若 [i−3,i][i-3,i] 顺序是 12341234，被四个 11 段替代，fi←fi−fi−4f_i\gets f_i-f_{i-4}。
若 [i−3,i][i-3,i] 顺序是 2314,3124,32142314,3124,3214，这三种情况只可能被 [i−4,i−1][i-4,i-1] 分段的情况替代，若 [i−4,i−1][i-4,i-1] 是正方形则 fi←fi−3fi−5f_i\gets f_i-3f_{i-5}。
若 [i−3,i][i-3,i] 顺序是 13241324，若 [i−2,i−1][i-2,i-1] 相邻，此时可以钦定为按 i−3,[i−2,i−1]i-3,[i-2,i-1] 分段。若 [i−4,i−1][i-4,i-1] 分段，能被 [i−4,i−3],[i−2,i−1][i-4,i-3],[i-2,i-1] 替代。若按 [i−5,i−4][i-5,i-4] 分段，能被 i−5,i−4i-5,i-4 替代；若按 [i−7,i−4][i-7,i-4] 分段，在 [i−7,i−5][i-7,i-5] 中必有两个相邻，可以 2+12+1 分段。因此可以转移 fi←fi−fi−4f_i\gets f_i-f_{i-4}，否则若 [i−5,i−1][i-5,i-1] 是正方形就转移 fi←fi−fi−5f_i\gets f_i-f_{i-5}。
若 [i−3,i][i-3,i] 顺序是 21342134，若 i−3,i−2i-3,i-2 相邻，钦定 [i−3,i−2],i−1,i[i-3,i-2],i-1,i 分段，[i−5,i−2][i-5,i-2] 分段的情况一定有 [i−5,i−4][i-5,i-4] 相邻，总是可以分成两段 22，因此已经被包含，转移 fi←fi−fi−4f_i\gets f_i-f_{i-4}。否则情况比较复杂：
如果能分段 [i−4,i−1][i-4,i-1]，就是 fi−4f_{i-4}。另一种方案是分段 i−1,ii-1,i 且 [i−5,i−2][i-5,i-2] 的顺序是 21432143（i−5,i−4i-5,i-4 必须交换，否则被 [i−4,i−1][i-4,i-1] 分段的情况覆盖）。我们已知 [i−3,i−2][i-3,i-2] 在交错的位置，因此 [i−5,i−2][i-5,i-2] 必须能成段。注意，此时我们的前提条件是扣除 [i−3,i][i-3,i] 成段的方案数。
现在我们考虑 [i−3,i][i-3,i] 成段时 [i−7,i−4][i-7,i-4] 要成段，考虑 i−7,i−6i-7,i-6 是否交换。若不交换，那这两个成段的限制已经满足，为 fi−8f_{i-8}。否则限制变为 [i−5,i−2],[i−7,i−4][i-5,i-2],[i-7,i-4] 要能成段且 i−7,i−6i-7,i-6 必须交换。发现这变成了一个子问题，我们可以拿一个 gig_i 算出，为 gi={gi−2+fi−4 [i−3,i] is valid0 otherwiseg_i=\begin{cases}g_{i-2}+f_{i-4}&\ [i-3,i]\text{ is valid}\\0&\ \text{otherwise}\end{cases}。转移就是 fi←fi−gi−4f_i\gets f_i-g_{i-4}。
若 [i−4,i−1][i-4,i-1] 不能分段，就只有分段 i−1,i,[i−5,i−2]i-1,i,[i-5,i-2]，比上面多一种 i−5,i−4i-5,i-4 不交换的情况 fi−6f_{i-6}。转移是 fi←fi−fi−6−gi−4f_i\gets f_i-f_{i-6}-g_{i-4}。
若被 [i−1,i][i-1,i] 分一段的某个方案替代（首先要求 i−1,ii-1,i 相邻）：
ii 不能留在原位，否则被上一种情况统计，因此只有 2143,12432143,1243 型。
对 12431243 型，可以钦定为按 [i−4,i−3],[i−2,i−1][i-4,i-3],[i-2,i-1] 分段。这要求 i−4i-4 是断点，和上面的讨论类似，若按 [i−6,i−3][i-6,i-3] 分段能拆成 2+22+2，若按 [i−7,i−4][i-7,i-4] 分段能将 [i−7,i−5][i-7,i-5] 拆成 i+2i+2。转移 fi←fi−fi−4f_i\gets f_i-f_{i-4}。
对 21432143 型，因为 [i−3,i−2][i-3,i-2] 也相邻，就能被 [i−3,i−2],[i−1,i][i-3,i-2],[i-1,i] 替代（同上，[i−5,i−2][i-5,i-2] 分段的情况被包含）。转移 fi←fi−fi−4f_i\gets f_i-f_{i-4}。
综上，我们做到了小常数 O(n)O(n)。
CPP
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int t,n,f[100005],g[100005];
char s[100005];
bool check2(int x){
  return x>=2&&(abs(s[x]-s[x-1])==3||(abs(s[x]-s[x-1])==1&&(s[x]+s[x-1])%3!=1));
}
bool check4(int x){
  if(x<4)return 0;
  int t=0;
  for(int i=0;i<4;i++)t|=1<<(s[x-i]-'0');
  return t==54||t==108||t==432||t==864;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),f[0]=1,cin>>t;
  while(t--){
    cin>>s+1,n=strlen(s+1);
    for(int i=1;i<=n;i++){
      g[i]=check4(i)?(g[i-2]+f[i-4])%mod:0,f[i]=f[i-1];
      if(check2(i))f[i]=(f[i]+f[i-2])%mod;
      if(check4(i)){
        f[i]=(f[i]+23ll*f[i-4])%mod;
        if(check4(i-1))f[i]=((f[i]-3ll*f[i-5])%mod+mod)%mod;
        if(check2(i-1))f[i]=(f[i]-f[i-4]+mod)%mod;
        else if(check4(i-1))f[i]=(f[i]-f[i-5]+mod)%mod;
        if(check2(i-2))f[i]=(f[i]-f[i-4]+mod)%mod;
        else{
          if(check4(i-1)){
            f[i]=(f[i]-f[i-5]+mod)%mod;
            if(check4(i-2))f[i]=(f[i]-g[i-4]+mod)%mod;
          }
          else f[i]=(f[i]-g[i-2]+mod)%mod;
        }
        if(check2(i))f[i]=(f[i]-2ll*f[i-4]%mod+2*mod)%mod;
      }
    }
    cout<<f[n]<<'\n';
  }
  return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...