Codeforces 356D Bacterial Melee dp

时间：2024-01-17 14:28:14

Bacterial Melee

我们发现所有合法串都是原序列的某个子序列（这个子序列相邻元素相等） 的扩展， 比如子序列为abc， 那么aabbbc, abbbcc 等都是合法串。

所以我们只需要dp出原串有多少相邻元素不同的子序列就好啦。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

int n, f[N][], g[N][];

int comb[N][N];

char s[N];

bool vis[];

inline void add(int &a, int b) {

    a += b; if(a >= mod) a -= mod;

}

int main() {

    for(int i = ; i < N; i++)

        for(int j = comb[i][] = ; j <= i; j++)

            comb[i][j] = (comb[i - ][j - ] + comb[i - ][j]) % mod;

    scanf("%d%s", &n, s + );

    f[][s[] - 'a'] = ; vis[s[] - 'a'] = true;

    for(int i = ; i <= n; i++) {

        memcpy(g, f, sizeof(g));

        for(int j = i - ; j >= ; j--) {

            for(int k = ; k < ; k++) {

                if(k != s[i] - 'a') add(f[j + ][s[i] - 'a'], g[j][k]);

            }

            add(f[j + ][s[i] - 'a'], mod - g[j + ][s[i] - 'a']);

        }

        if(!vis[s[i] - 'a']) {

            vis[s[i] - 'a'] = true;

            f[][s[i] - 'a'] = ;

        }

    }

    int ans = ;

    for(int i = ; i <= n; i++)

        for(int j = ; j < ; j++)

            add(ans, 1ll * comb[n - ][i - ] * f[i][j] % mod);

    printf("%d\n", ans);

    return ;

}

/*

*/

相关文章