arc119f题解

· · 题解

arc119f

AtCoder Express 3

自动机写法。开始在做的时候题解没讲每个节点代表什么状态，自己推了一遍，记录一下。

思路

计数，求有多少种替换方式使得 0 到 n 存在一条长度小于等于 K 的路径。

可以做 O(n^3) 的 dp。设 dp_{i,a,b} 表示前 i 个位置，最近的 A 和 B 分别在 a 和 b。官方题解是优化 a 和 b，发现有意义状态下 a 和 b 的差不超过一定数值。

观察发现，在 \text{BAA...AAB} 处，肯定选择从 B 直接跳过去。具体的，当有连续的 4 个 A 后，会选择直接从两端的 B 越过。所以有效的状态并不多。

考虑建一个自动机来求出任意状态对应的下一个状态。由于 A 和 B 可以取反得到，先只考虑当前在 A，在 B 同理。以下几种有用状态。

综上，有 13 种有用状态。

考虑转移。记 tree_{i,0/1} 表示当前状态为 i，加入 A 或 B，走向哪一个状态，val_{i,0/1} 为转移的代价。

分析完自动机状态的转移，dp 即可。设 dp_{i,j,k} 表示加入前 i 位，走了 j 步，当前状态为 k。

dp_{0,0,12}=1 dp_{i+1,j+val_{k,0},tree_{k,0}}+=dp_{i,j,k} dp_{i+1,j+val_{k,1},tree_{k,1}}+=dp_{i,j,k}

注意到加入一位并不是走到一位。状态设定的当前走到的点不是状态的最后一位。记录 dis 表示状态的最后一位是 n-1，状态设定的当前走到的点离终点的距离，稍微处理即可。

复杂度 O(13nk)。

code

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int maxn=4010;
const int inf=1e9;
inline int read(){
    int x=0,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-48);ch=getchar();}
    return x*f;
}

int n,m,ans;
char c[maxn];
int tree[15][2],val[15][2];
int dis[7];
int dp[maxn][maxn][15];

int T;
signed main(){
    //  freopen(".in","r",stdin);
    //  freopen(".out","w",stdout);

    n=read();m=read();
    scanf("%s",c+1);
    tree[0][0]=2;val[0][0]=0;tree[0][1]=8;val[0][1]=0;
    tree[2][0]=4;val[2][0]=0;tree[2][1]=8;val[2][1]=1;
    tree[4][0]=6;val[4][0]=1;tree[4][1]=12;val[4][1]=2;
    tree[6][0]=6;val[6][0]=0;tree[6][1]=1;val[6][1]=1;
    tree[8][0]=12;val[8][0]=1;tree[8][1]=7;val[8][1]=0;
    tree[10][0]=6;val[10][0]=0;tree[10][1]=12;val[10][1]=1;
    tree[12][0]=10;val[12][0]=0;tree[12][1]=11;val[12][1]=0;
    for(int i=0;i<=5;i++){//状态取反。
        for(int k=0;k<=1;k++){
            if(tree[i*2][k^1]==12)tree[i*2+1][k]=tree[i*2][k^1];
            else tree[i*2+1][k]=tree[i*2][k^1]^1;
            val[i*2+1][k]=val[i*2][k^1];
        }
    }
//  for(int i=0;i<=12;i++)cout<<tree[i][0]<<" "<<val[i][0]<<" "<<tree[i][1]<<" "<<val[i][1]<<"\n";
    dis[0]=dis[3]=dis[4]=dis[5]=dis[6]=1;
    dis[1]=dis[2]=2;
    dp[0][0][12]=1;
    for(int i=0;i<=n-2;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=12;k++){
                if(dp[i][j][k]){
                    if(c[i+1]=='A'){
                        dp[i+1][j+val[k][0]][tree[k][0]]+=dp[i][j][k];
                        dp[i+1][j+val[k][0]][tree[k][0]]%=mod;
                    }
                    else if(c[i+1]=='B'){
                        dp[i+1][j+val[k][1]][tree[k][1]]+=dp[i][j][k];
                        dp[i+1][j+val[k][1]][tree[k][1]]%=mod;
                    }
                    else{
                        dp[i+1][j+val[k][0]][tree[k][0]]+=dp[i][j][k];
                        dp[i+1][j+val[k][0]][tree[k][0]]%=mod;
                        dp[i+1][j+val[k][1]][tree[k][1]]+=dp[i][j][k];
                        dp[i+1][j+val[k][1]][tree[k][1]]%=mod;
                    }
                }
            }
        }
    }
    for(int j=0;j<=m;j++){
        for(int k=0;k<=12;k++)if(j+dis[k>>1]<=m){
            ans+=dp[n-1][j][k];
            ans%=mod;
        }
    }
    printf("%lld\n",ans);
}