【CF660E】Different Subsets For All Tuples

題意：對于所有長度為n，每個數(shù)為1,2...m的序列，求出每個序列的本質(zhì)不同的子序列的數(shù)目之和。（多個原序列可以有相同的子序列）

$n,m\le 10^6$

題解：結(jié)論：一個子序列出現(xiàn)的次數(shù)只與其長度有關(guān)。

我們可以分別求出每種長度的子序列出現(xiàn)的總次數(shù)，顯然答案為：

$\sum\limits_{i=1}^nm^i\sum\limits_{j=i}^nC_{j-1}^{i-1}(m-1)^{j-i}m^{n-j}$

（上面沒有考慮k=0，一會要單獨(dú)計(jì)算）

繼續(xù)化簡

$\sum\limits_{j=1}^nm^{n-j}\sum\limits_{i=1}^jC_{j-1}^{i-1}(m-1)^{j-i}m^i$

$\sum\limits_{j=1}^nm^{n-j+1}(2m-1)^{j-1}$

就完事了。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll P=1000000007;
ll f1[1000010],f2[1000010],ans;
int n,m;
int main()
{
	scanf("%d%d",&n,&m);
	int i;
	for(f1[0]=f2[0]=i=1;i<=n;i++)	f1[i]=f1[i-1]*m%P,f2[i]=f2[i-1]*(m+m-1)%P;
	for(ans=f1[n],i=1;i<=n;i++)	ans=(ans+f1[n-i+1]*f2[i-1])%P;
	printf("%lld",ans);
	return 0;
}