P1758

Aryper · 2021-11-01 21:04:36 · 个人记录

[NOI2009] 管道取珠

尝试转移 \sum a_i^2，拆和式，等等奇怪的方法，最终搞不出来。

这个方法令我大为震撼。。。确实有点神。。。

所谓 \sum a_i^2 的意义，就是取两次球，结果得到的序列相同的方案数。

然后就非常好做了。

定义 f(i,j,k,l) 表示第一次上管取了 i 个球，下管取了 j 个球，第二次上管取了 k 个球，下管取了 l 个球，且两次的序列相同的方案数。

然后就随便转移了。

因为这个状态稍微有点大，我们发现 i+j=k+l 可以弄掉一维，最后把 i 那一维用滚动数组滚掉就好了。

时间复杂度 O(n^3)。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=5e2,mo=1024523;

ll n,m;

ll f[2][N+5][N+5];

char s1[N+5],s2[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();

    scanf("%s",s1+1);scanf("%s",s2+1);

    f[0][0][0]=1;

    for(ll i=0;i<=n;i++) {
        for(ll j=0;j<=m;j++) {
            for(ll k=0;k<=n;k++) {
                ll l=i+j-k;if(l<0||l>m) continue;
                if(i>=1&&k>=1&&s1[i]==s1[k]) f[i&1][j][k]=(f[i&1][j][k]+f[(i-1)&1][j][k-1])%mo;
                if(i>=1&&l>=1&&s1[i]==s2[l]) f[i&1][j][k]=(f[i&1][j][k]+f[(i-1)&1][j][k])%mo;
                if(j>=1&&k>=1&&s2[j]==s1[k]) f[i&1][j][k]=(f[i&1][j][k]+f[i&1][j-1][k-1])%mo;
                if(j>=1&&l>=1&&s2[j]==s2[l]) f[i&1][j][k]=(f[i&1][j][k]+f[i&1][j-1][k])%mo;
            }
        }
        for(ll j=0;j<=m;j++) {
            for(ll k=0;k<=n;k++) {
                f[(i+1)&1][j][k]=0;
            }
        }
    }

    write(f[n&1][m][n]);

    return 0;
}