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

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 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
int n, m, k, pr[26];
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 = 0;
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+1)%mod;
return (sum(r)-sum(l-1)+mod)%mod;
}
} bit;
void extend(int x, int c) {
int pos = s[x-1]-'a' == c ? x-1 : pr[c];
int val = bit.query(pos, x-1);
bit.modify(x, val);
if(x > 1) pr[s[x-1]-'a'] = x-1;
}
int main() {
scanf("%d%d", &n, &k);
scanf("%s", s + 1);
m = strlen(s + 1);
for(int i = 1; i <= m; i++)
extend(i, s[i]-'a');
for(int i = m+1; i <= m+n; i++) {
int z = -1;
for(int j = 0; j < k; j++) {
if(j != s[i-1] - 'a') {
if(z == -1 || pr[z] > pr[j]) z = j;
}
}
if(z == -1) z = 0;
s[i] = 'a' + z;
extend(i, z);
}
printf("%dn", bit.query(0, n + m));
return 0;
}
/*
*/