ABC 171 F - Strivore 【容斥】

https://atcoder.jp/contests/abc171/tasks/abc171_f

题意

给你一个数 \(k\) ，一个字符串 \(s\) （只包含小写字母）

定义一次操作：把任意小写英文字母填入当前串的任意位置。问做完 \(k\) 次操作能得到多少不同的字符串？

思路

首先试着直接求出答案，那么就是往当前串的空隙里插入字符。

原字符串的空隙一共有 \(|S|\) 个。对于字符串原有的字符 \(s_i\) 来说，它会把它之后第一次出现的和 \(s_{i+1}\) 相同的字符当成 \(s_{i+1}\)，所以除了最后一个空隙可以任意填（26种），原字符串的空隙可以填入的字符都是25种。

我的意思是 \(\sum_{i=0} ^ {k} 26^i * 25^{k - i} * C_{k - i + |S| - 1} ^ {|S| - 1}\) 。

然而可以证伪。

因为我的做法是对于同一个 \(i\)，把所有的排列组合方案数和 \(25^{k - i}\) 相乘，可能会多算，例如 _a_b , 填入了aa，填在a之后就都可以，有填的a落在a之前就不可以。

正解：

正难则反。

ans = \(26^{k + |S|}\) - 不包含 \(S\) 这个子序列的字符串方案数

check是否包含 \(S\) 这个子序列的方法：从字符串的第一个开始找，找到和 \(s_i\) 相同的字符串后，\(i\) += 1

新字符串可以包含 \(S\) 这个子序列的一个前缀 from 0 to |S| - 1

字符串的空隙间可以填入25种字符，由于不包含完整的 \(S\)，字符串的末尾的空隙也只能填入25种字符

ans = \(26^{k + |S|} - \sum_{i = 0} ^ {|S| - 1} 25^{k + |S| - i} * C_{k + |S|} ^ {i}\)

code

思路清楚了，代码实现就比较简单了。

ll qpow(ll a, ll x) {

	ll ans = 1;

	while(x) {

		if(x & 1) {ans *= a; ans %= mod;}

		a *= a; a %= mod; x /= 2;

	}

	return ans;

}

void init(int n) {

	fac[0] = 1;

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

		fac[i] = fac[i - 1] * i % mod;

	}

	inv[n] = qpow(fac[n], mod - 2);

	for(int i = n - 1; i >= 1; i--) {

		inv[i] = inv[i + 1] * (i + 1) % mod;

	}

	inv[0] = 1;

}

ll C(int n, int m) {

    if(n < m) return 0;

    return fac[n] * inv[m] % mod * inv[n - m] % mod;

}

int main () {

    init(2e6);

    scanf("%d%s", &k, s + 1);

    n = strlen(s + 1);

    ll ans = qpow(26, n + k);

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

        ans = (ans - qpow(25, n + k - i) * C(n + k, i) % mod + mod) % mod;

    }

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

    return 0;

}

巴特西

ABC 171 F - Strivore 【容斥】

题意

思路

code

最新文章

热门文章