牛客14599 - 子序列

• 链接：https://ac.nowcoder.com/acm/problem/14599
• 知识点：组合数学
• 难度：蓝

题意

• 给出一个小写字母字符串 T，长度为 $nn$。
• 求有多少长度为 $m(m\le 10^5)m\; (m\backslash leq10^5)$ 的小写字母字符串 S，满足 T 是 S 的一个子序列。

思路

错误思路

• 利用排列组合公式，先确定原字符串 T 中每个字母的位置，再确定剩下的空位放什么。但是去重麻烦。

初步思路

• 我们从合法的新串下手，考虑制定出一种方法来从中找出原串。

• 对这种方法的要求是：按照这种方法 找出的新串 的下标 必须唯一。

• 一种合理的匹配方式是：

  • 假如原串是：$abcabc$
  • 假如新串是：$aaabbbcccaaabbbccaaccaaabbbcccaaabbbccaacc$
  • 匹配应该是：$aaabbbcccaa[a]bb[b]ccaac[c]aaabbbcccaa[a]bb[b]ccaac[c]$
  • 匹配规则是：对于某个被匹配到的字符 $chch$ 开始，从它右边第一个开始，到它右边下一个被匹配的字符左边第一个为止，不得出现跟 $chch$ 相同的字符。
  • 能发现，按照这种方法 找出的新串 的下标是唯一的。
  • 总结一下这种匹配方式：

  • • 我们知道，由子序列 $SS$ 构造原序列 $TT$，问方案数这类问题，就是要保证，
    • 如果你在 $TT$ 确定 $TT$ 的第 $ii$ 个字符 $t_{i}t\_i$，匹配的是 $SS$ 中的第 $pp$ 个字符 $s_{p}s\_p$，
    • 并且你在 $TT$ 确定 $TT$ 的第 $jj$ 个字符 $t_{j}t\_j$，匹配的是 $SS$ 中的第 $p+1p+1$ 个字符 $s_{p+1}s\_\{p+1\}$，
    • 除了 $t_i=s_{p}t\_i=s\_p$，$t_j=s_{p+1}t\_j=s\_\{p+1\}$ 以外，还要保证，$t_{i+1}\mathrm{.}\mathrm{.}\mathrm{.}{t}_{j-1}t\_\{i+1\}...t\_\{j-1\}$ 的所有字符，都不包含 $t_{i}t\_i$。

• 现在考虑按照这种匹配思路，从原串开始，构造新串。

继续思考

• 如果数据范围不大，使用 DP 可以实现。

void Sol()
{
	dp[0][0] = 1;
	for (int i=1; i<=m; i++)    //从你决定开始匹配原串第一个字符之前，放什么都行，每一个位置有26种放法。
	{
		dp[i][0] = dp[i-1][0] * 26 % MOD;
	}
	
	for (int i=1; i<=m; i++)//枚举新串
	{
		for (int j=1; j<=min(i, n); j++)//枚举原串
		{
            //对于新串的第 i 个字符，有两种情况：
            //一种是第i个字符匹配上原串的第j个字符
            //一种是第i个字符在前i-1个已经匹配上原串的第j个字符的情况下，有25种放法。
			dp[i][j] += (j-1<0?0:dp[i-1][j-1]) + dp[i-1][j] * 25 % MOD, dp[i][j] %= MOD;
		}
	}
	printf("%lld\n",dp[m][n]);
}

最终思路

• 还是利用排列组合公式，先确定原字符串 T 中每个字母的位置，再确定剩下的空位放什么。
• 然后，我们不妨规定：对于一个空缺的位置，不允许放位于它左边的第一个已经安放好的字母，其它字母随便放。
• 对于某一个字母的周围出现和这个字母一样的字母的情况，这种做法能控制 重复的字母一定位于它的左边。
• 我们还发现。如果原串第一个字母被安放到了位置 $pp$，那么位置区间 $[1,p)[1,p)$ 所有字母都能放，其它空位只能放 $2525$ 种。
• 枚举第一个字母的位置，再利用组合数安放剩下的字母。接下来的操作见上一条。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#define int long long
const int N		= 1e6+10;
const int MOD	= 1000000007;
using namespace std;

long long bin[N];
void Init()
{
	bin[0]=1; 
	bin[1]=1;
	for(int i=2;i<N;i++)
		bin[i]=i*bin[i-1]%MOD;
}
long long POW(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1)
		{
			res*=a, res%=MOD;
		}
		b>>=1;
		a*=a, a%=MOD;
	}
	return res;
}
long long C(long long n, long long m)//求C(n,m) n在下，m在上。注意在这之前加init函数
{
	return (bin[n]%MOD)*(POW(bin[m]*bin[n-m]%MOD,MOD-2))%MOD;
}

char str[N];
int n, m;

void Solve()
{
	int ans = 0;
	for (int i=1; i<=m-n+1; i++)
	{
		ans += C(m-i,n-1) * POW(25, m-i-n+1) % MOD * POW(26, i-1) % MOD, ans%=MOD;
	}
	printf("%lld\n",ans);
}

signed main()
{
	Init();
	scanf("%s",str+1);
	n = strlen(str+1);
	scanf("%lld",&m);
	Solve();
	return 0;
}