CF 660E Different Subsets For All Tuples

题目描述

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

简要题意：给定 $n,m$，求所有长度为 $n$ 的每个位置为 $[1,m]$ 的序列的价值和，定义一个序列的价值为其本质不同的子序列的数量

$n,m\le 10^6$

Solution

我们首先考虑一个比较暴力的做法，我们枚举子序列的长度的长度 $i$，同时对于每个子序列，我们在其第一次出现的结束位置计数，我们令这个位置为 $j$，那么我们可以得到如下式子 $ans=\sum_{i=1}^nm^i\sum_{j=i}^n\binom{j-1}{i-1}(m-1)^{j-i}m^{n-j}$，组合数枚举的是子序列出现的位置，$(m-1)^{j-i}$ 表示除了这个子序列之外其他数的选择方案，注意到每个位置的不能与其后第一个属于该子序列的数相同，其他 $m-1$ 种数都可以选，$m^{n-j}$ 表示后面可以随便填，我们考虑化简

$$\begin{aligned} \sum_{i=1}^nm^i\sum_{j=i}^n\binom{j-1}{i-1}(m-1)^{j-i}m^{n-j}&=\sum_{i=1}^n\sum_{j=i}^n\binom{j-1}{i-1}(m-1)^{j-i}m^{n-j+i}\\ &=\sum_{j=1}^n\sum_{i=1}^j\binom{j-1}{i-1}(m-1)^{j-i}m^{n+i-j}\\ &=\sum_{j=0}^{n-1}\sum_{i=0}^{j}\binom{j}{i}(m-1)^{j-i}m^{n+i-j}\\ &=\sum_{j=0}^{n-1}m^{n-j}(2m-1)^j \end{aligned}$$

这个式子我们直接暴力即可

#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;
}