CROC 2016 - Elimination Round (Rated Unofficial Edition) E

E - Intellectual Inquiry

思路：我自己YY了一个算本质不同子序列的方法，发现和网上都不一样。

我们从每个点出发向其后面第一个a, b, c, d ...连一条边，那么总的不同子序列就是从0号点出发能走出多少条

不同点的路径。 dp[ i ]表示是到 i 这个点的不同路径数，构成的图显然是个DAG，把这个dp出来就好啦。最后补

n个就是贪贪心。

网上的另外两种方法。

dp[ i ] 表示[1, i] 的字符串有多少不同子序列。

dp[ i ] = dp[i - 1] * 2 - dp[ pre[s[ i ] ] - 1]

dp[ i ][ j ]表示[1, i] 的字符串末尾为 j 的不同子序列有多少种。

如果s[ i ] != j dp[ i ][ j ] = dp[ i - 1] [ j ]

否则 dp[ i ] [ j ] = (dp[ i - 1][ 0 ] + dp[ i - 1][ 1 ].... + dp[ i - 1][ k - 1]) + 1

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define PLI pair<LL, int>

#define ull unsigned long long

using namespace std;

const int N = 2e6 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

int n, m, k, pr[];

char s[N];

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

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

}

struct Bit {

    int a[N];

    void modify(int x, int v) {

        for(int i = x; i < N; i+=i&-i)

            add(a[i], v);

    }

    int sum(int x) {

        int ans = ;

        for(int i = x; i; i-=i&-i)

            add(ans, a[i]);

        return ans;

    }

    int query(int l, int r) {

        if(!l) return (sum(r)+mod+)%mod;

        return (sum(r)-sum(l-)+mod)%mod;

    }

} bit;

void extend(int x, int c) {

    int pos = s[x-]-'a' == c ? x- : pr[c];

    int val = bit.query(pos, x-);

    bit.modify(x, val);

    if(x > ) pr[s[x-]-'a'] = x-;

}

int main() {

    scanf("%d%d", &n, &k);

    scanf("%s", s + );

    m = strlen(s + );

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

        extend(i, s[i]-'a');

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

        int z = -;

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

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

                if(z == - || pr[z] > pr[j]) z = j;

            }

        }

        if(z == -) z = ;

        s[i] = 'a' + z;

        extend(i, z);

    }

    printf("%d\n", bit.query(, n + m));

    return ;

}

/*

*/

巴特西

CROC 2016 - Elimination Round (Rated Unofficial Edition) E - Intellectual Inquiry dp

最新文章

热门文章