21.10.10模拟 字符串

给定一个长度为n的字符串，串中的字符保证是前k个小写字母。你可以在字符串后再添加m个字符，使得新字符串所包含的不同的子序列数量尽量多。当然，前提是只能添加前k个小写字母。求新的长度为n+m的串最多的不同子序列数量。答案对1e9+7取模。

一直想不明白怎么加串。。后来发现对于要加的直接贪心找每种字符加上后的最优结果。

怎么求本质不同的子序列呢？

我们可以设last_i为字符s[i]上一次出现的位置，f_i为第i为结尾新出现的不同子序列数量

考虑新加入一个i，那么第x位结尾
(last[i] le x le i-1) 新出现的子序列都可以加上i得到一个新的

怎么样证明这样不会产生重复的子序列呢
反证法
如果如果以last[i] − 1之前的某个位置为结尾的子序列接上第i位，会产生一个新的子序列，那么之前的子序列直接加上last[i] 也可以产生这个新的子序列。
这与这个子序列在i第一次出现矛盾

(f[i]=sum^{i-1}_{j=last[i]} f[j])

前缀和优化

f[i]表示枚举到第i位所有本质不同子序列数量，考虑第i位的数字a[i]要不要加

如果a[i]没出现过，那么f[i]就是相当于比f[i-1]多了一倍，而且还多了a[i]这个长度为1的子序列

如果a[i]出现过,那么就容斥减去

	rep(i, 2, len) {
		if(!last[a[i]]) f[i] = 1ll * f[i - 1] * 2 % mod + 1;
		else f[i] = 1ll * f[i - 1] * 2 % mod - f[last[a[i]] - 1];
		if(f[i]<mod) f[i]+=mod;
		if(f[i]>mod) f[i]%=mod;
		last[a[i]]=i;
	}

本题就是后面m个多了个枚举字符。

int m, k, ans = 1, n;
int f[N], last[N];
int main() {
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
	cin >> m >> k;
	char ch;
	while(cin >> ch) {
		int x = ch - 'a' + 1;
		if(x < 1 || x > 26) break;
		int tmp = ans;
		ans = (ans*2%mod - f[x] + mod) % mod;
		f[x] = tmp;
		last[x] = ++n;
	}

	rep(i, 1, m) {
		int x(0);
		rep(j, 1, k) {
			if(!x || last[x] > last[j]) x = j; //Ì°ÐÄÕÒ×îÇ°ÃæµÄ
		}
		last[x] = ++n;
		int tmp = ans;
		ans = (ans*2%mod - f[x] + mod) % mod;
		f[x] = tmp;
	}
	cout << ans << '
';
	return 0;
}