题目概述

求长度为 $n$ ，元素值域为 $[1,m]​$ 的所有序列的本质不同子序列的个数的和。

解题报告

不难发现长度为 $i$ 的子序列的出现次数是相同的，所以我们可以只统计均为 $1$ 的子序列，这个非常容易统计，令 $f_i$ 表示长度为 $i$ 的均为 $1$ 的子序列的出现次数，那么 $f_i={n\choose i}(m-1)^{n-i}+f_{i+1}$（前面的式子表示选 $i$ 个位置放 $1$ ，其余地方不放 $1$ 的方案数（只统计了 $1$ 的个数为 $i$ 的情况）。后面的式子表示 $1$ 的个数 $>i$ 的方案数）。

最后的答案就是 $\sum_{i=0}^{n}f_im^i$ 。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000000,MOD=1e9+7;

int n,m,pw[2][maxn+5],fac[maxn+5],INV[maxn+5],f[maxn+5],ans;

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD;
    pw[0][0]=1;for (int i=1;i<=n;i++) pw[0][i]=(LL)pw[0][i-1]*m%MOD;
    pw[1][0]=1;for (int i=1;i<=n;i++) pw[1][i]=(LL)pw[1][i-1]*(m-1)%MOD;
}
#define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD)
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);Make(n);f[n]=1;f[0]=pw[0][n];
    for (int i=n-1;i;i--) AMOD(f[i]=(LL)C(n,i)*pw[1][n-i]%MOD,f[i+1]);
    for (int i=0;i<=n;i++) AMOD(ans,(LL)pw[0][i]*f[i]%MOD);printf("%d\n",ans);return 0;
}