几何

几何

比赛时候唐了，连状态都没想到。

记录一下 dp 的惯用优化方法。

思路

（此处串 \(x,y\) 从 \(0\) 开始，串 \(s\) 从 \(1\) 开始）

设 \(dp[i][j][k]\) 为第 \(i\) 位时，将 \(s[1,i]\) 分为，串 \(x\) 重复若干次加上串 \(x[0,j-1]\)，串 \(y\) 重复若干次加上串 \(y[0,k-1]\)，的可行性。

如果可以就是 \(1\)，不可以就是 \(0\)。

若 \(s[i]==x[j]\)，有 \(dp[i+1][(j+1)\mod len_x][k]|=dp[i][j][k]\)。

若 \(s[i]==y[k]\)，有 \(dp[i+1][j][(k+1)\mod len_y]|=dp[i][j][k]\)。

这样做会超时，考虑优化。

把 \(k\) 放进状态里。

设状态 \(f[i][j]\) 同上，值为一个二进制数，若二进制数第 \(k\) 位为 \(1\)，那么表示 \(dp[i][j][k]=1\)。

这样子就把第三维压进了状态里。

对于 \(s[i]==x[j]\)，有 \(f[i+1][(j+1)\mod len_x]|=f[i][j]\)。

对于第二种转移，\(f[i][j]<<1\) 中为 \(1\) 的位（\(len_y\) 这一位为 \(1\)，则循环位移到第 \(0\) 位）即为可以取到的 \(y[k]\)。可以设一个 \(g[x]\) 表示字符 \(x\) 在串 \(y\) 中出现位置的状压，这样就有 \(f[i+1][j]|=(f[i][j]<<1)\& g[s[i]]\)。

于是就可以愉快的 AC 了。

CODE

#include<bits/stdc++.h>
using namespace std;#define ll long longconst int maxn=5e5+5;int ns,nx,ny;char s[maxn],x[maxn],y[maxn];ll f[maxn][60],g[30];inline ll work(ll x)
{ll op=(x>>(ny-1))&1;x^=(op<<(ny-1));x=(x<<1)|op;return x;
}
inline void clr()
{for(int i=0;i<=ns+1;i++) for(int j=0;j<=nx+1;j++) f[i][j]=0;for(int i=1;i<=26;i++) g[i]=0;
}
int main()
{int _;scanf("%d",&_);while(_--){cin>>s+1>>x>>y;ns=strlen(s+1),nx=strlen(x),ny=strlen(y);clr();for(int i=0;i<ny;i++) g[y[i]-'a'+1]^=1ll<<i;f[0][0]=1;for(int i=1;i<=ns;i++){int ch=s[i]-'a'+1;for(int j=0;j<nx;j++){if(s[i]==x[j]){f[i][(j+1)%nx]|=f[i-1][j];}ll st=f[i-1][j]&g[ch];f[i][j]|=work(st);}}if(f[ns][0]&1) puts("Yes");else puts("No");}
}