DDOSvoid's Blog

CF 660E Different Subsets For All Tuples

发表于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/660/E

简要题意：给定 $n,m$，现在要求所有长度为 $n$ 的序列，序列中每个位置只能填 $[1,m]$，的本质不同的子序列的个数的和

$n,m\le 10^6$

Solution

我们考虑对于每种子序列在其出现的序列中的第一次出现位置来计数，不妨令第一次出现的结束位置为 $i$，子序列的长度为 $j$，那么我们首先有 $\binom{i-1}{j-1}m^{j+n-i}$，显然 $[i+1,n]$ 都是随便选，然后这个这样的子序列有 $m^j$ 种，出现位置的选择有 $\binom{i-1}{j-1}$，现在的问题是 $[1,i]$ 中剩下的 $i-j$ 个位置要如何填，简单思考可以发现每个位置只有一个数不能填，即它后面的第一个属于我们枚举的子序列的位置的那个数，所以答案为 $\sum_{i=1}^n\sum_{j=1}^i\binom{i-1}{j-1}m^{j+n-i}(m-1)^{i-j}$，注意这个式子没有加上空子序列的答案，所以我们计算完后需要再加上 $m^n$，能够发现这个式子很像二项式定理，我们考虑向这个方向化简这个式子

时间复杂度 $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#define maxn 1000010
using namespace std;

const int p = 1000000007;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }
int pow_mod(int x, int n) {
    int s = 1;
    for (; n; n >>= 1, x = mul(x, x))
        if (n & 1) s = mul(s, x);
    return s;
}

int n, m; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; int ans = 1, inv = pow_mod(m, p - 2); 
    for (int i = 0; i < n; ++i) ans = add(ans, pow_mod(add(2, p - inv), i));
    cout << mul(ans, pow_mod(m, n)) << "\n";
    return 0;
}