一个页面对网站如何建设,wordpress可以做电影站,专业集团门户网站建设方案,标志设计图案这题本质上还是数据结构。
首先看到这个 2 n 2\times n 2n的网格图就很容易想到分治。我们还是考虑把要统计的东西变得可视化#xff0c;一条路径要么穿过中线一次#xff0c;那么我们可以将两边的串拼起来得到答案#xff1b;要么穿过中线两次#xff0c;考虑其中一边的…这题本质上还是数据结构。
首先看到这个 2 × n 2\times n 2×n的网格图就很容易想到分治。我们还是考虑把要统计的东西变得可视化一条路径要么穿过中线一次那么我们可以将两边的串拼起来得到答案要么穿过中线两次考虑其中一边的路径是固定的那么我们枚举两个端点再判断一下和原串是否匹配的上就做完了。那么考虑预处理出 d p i , j , 0 / 1 , 0 / 1 dp_{i,j,0/1,0/1} dpi,j,0/1,0/1表示从位置 ( 1 / 2 , i ) (1/2,i) (1/2,i)开始匹配长度为 j j j向左/右走的方案数这事实上非常好转移可以自己编一下。当然可能还要把串正着和倒着处理一边总之挺麻烦的。
将网格图翻转后做两次即可得到答案。求 L c p Lcp Lcp可以用暴力 d p dp dp代替。事实上也并不需要分治。注意不要算重。
细节题贼容易写挂。
复杂度 O ( n 2 ) O(n^2) O(n2)。
#includebits/stdc.h
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
#define db double
#define cpx complexdb
using namespace std;
const int mod1e97;
const int N2005;
int n,K,Right[2][N][N],Left[2][N][N],dpl[2][N][N],res;
string s[2],str;
void add(int x,int y){x(xy)%mod;
}
void solve(){for(int i0;i2;i){for(int jn-1;j0;j--){for(int k0;kK;k){Right[i][j][k](s[i][j]!str[k])?0:((j!n-1k1)?(Right[i][j1][k-1]1):1);}}}for(int i0;i2;i){for(int j0;jn;j){for(int k0;kK;k){Left[i][j][k](s[i][j]!str[k])?0:((j1k1)?(Left[i][j-1][k-1]1):1);}}}memset(dpl,0,sizeof dpl);for(int i0;i2;i){for(int j0;jn;j){if(s[i][j]str[0]){dpl[i][j][0]1;}}}//fixedfor(int i0;in;i){for(int ji;jn;j){for(int k0;k2;k){//strangeif(Left[k][j][2*(j-i1)-1]j-i1Right[k^1][i][j-i]j-i1){add(dpl[k][j][2*(j-i1)-1],1);}}}}for(int k1;kK;k){for(int i0;i2;i){for(int j0;jn;j){if(s[i][j]str[k]){if(j)add(dpl[i][j][k],dpl[i][j-1][k-1]);if(s[i^1][j]str[k-1]){if(jk-20)add(dpl[i][j][k],dpl[i^1][j-1][k-2]);}}}}}
}
void getans(){//fixedfor(int i0;i2;i){for(int j0;jn;j){add(res,dpl[i][j][K-1]);}}for(int i1;in;i){for(int ji1;jn;j){for(int k0;k2;k){if(Right[k][i][K-1]j-i1K-(j-i2)0Left[k^1][j][K-(j-i2)]j-i1K-2*(j-i1)-10){add(res,dpl[k^1][i-1][K-2*(j-i1)-1]);}}}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cins[0]s[1]str,ns[0].size(),Kstr.size();//fixedif(K1){for(int i0;i2;i){for(int j0;jn;j){if(s[i][j]str[0]){add(res,1);}}}coutres;return 0;}if(K2){for(int i0;i2;i){for(int j0;jn-1;j){if(s[i][j]str[0]s[i][j1]str[1]){add(res,1);}if(s[i][j1]str[0]s[i][j]str[1]){add(res,1);}}}for(int i0;i2;i){for(int j0;jn;j){if(s[i][j]str[0]s[i^1][j]str[1]){add(res,1);}}}coutres;return 0;}//fixedsolve();getans();//fixedswap(s[0],s[1]),reverse(s[0].begin(),s[0].end()),reverse(s[1].begin(),s[1].end());solve();getans();coutres\n;
}
