【2020NOI.AC省选模拟#9】C. 重复

题目链接

原题解：

通过计数相同的子序列对个数的方式来计算答案。

设$f(i,j)$为$S$的前$i$和$j$个字符的公共子序列对个数。

当$S_i=S_j$时，$f(i,j)=f(i,j-1)+f(i-1,j)$。

否则，$f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)$。

还可以通过依次将$i$和$j$一次一步地移到下一个配对的字符的位置的方式转移，复杂度为$O(n^2)$。

补充：

$f$数组只能用int而不能用long long，不然会爆空间。

代码（100分）：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define IL inline

#define RG register

using namespace std;

#define RI RG int

#define RC RG char

const int N=1e4;

    int n,a[N+3],mod;

IL bool insigma(RC ch){

    return 33<=ch&&ch<=126;

}

    int f[N+3][N+3];

IL int add(RI x,RI y){

    return (x+=y)>=mod?x-=mod:x;

}

int main(){

    n=0;

    for(RC ch=getchar();insigma(ch);ch=getchar())

        a[++n]=ch;

    scanf("%d",&mod);

    for(RI i=0;i<=n;i++)

        f[0][i]=1;

    for(RI i=1;i<=n;i++){

        for(RI j=1;j<=n;j++){

            f[i][j]=f[i][j-1];

            if(a[i]==a[j])

                f[i][j]=add(f[i][j],f[i-1][j-1]);

        }

        for(RI j=0;j<=n;j++)

            f[i][j]=add(f[i][j],f[i-1][j]);

    }

    printf("%d",f[n][n]);            

    return 0;

}

【2020NOI.AC省选模拟#9】C. 重复的相关教程结束。