Different Subsets For All Tuples 数学
题面
有一个长度为\(n\)的数列,每个位置上数字的值在\([1,m]\)范围内,则共有\(m^n\)种可能的数列。分别求出每个数列中本质不同的子序列个数(包含空序列),然后求和,答案对\(10^9+7\)取模。(\(1\le n,m\le10^6\))
数据范围
$ 1<=n,m<=10^{6} $
解法
显然,我们需要求每个子序列的贡献,空序列的贡献很简单,就是\(m^n\)。然后我们处理非空的,但我们会发现,很容易重复,比如子序列1,在11这个序列中出现了两次,但其贡献显然只有1,那该如何处理呢?这里有一个非常实用且常用的技巧,就是我们把这个子序列的下标处理成一个字符串,我们只去计算每种序列里字典序最小的那个,这样就避免重复了。
于是我们应该怎么搞呢?首先我们把长度为\(len\)子序列的下标记为\(pos_1……pos_{len}\),然后把整个字符串分为两部分,第一部分是\(1—pos_{len}\),第二部分是剩下的。
对于第一部分,我们假设除开作为子序列的,还有\(a\)个字符位置,那么这些字符的选择只有\(m-1\)个,然后这个问题就转化成了把\(a\)个小球放到\(len\)个盒子里,且允许有空的,个数为\(C_{a+len-1}^{len-1}\)。
对于第二部分,我们就随便乱填,个数为\(m^{n-len-a}\)。
综上,我们得出一个式子,\(ans=\sum_{i=1}^{n}\sum_{j=0}^{n-i}C_{i+j-1}^{i-1}*(m-1)^{j}*m^{n-i-j}*m^i\)。这样子求就T飞了,于是我们想个办法化简一下。
首先换元,这一步我们要尽量让组合数的表达式简单点,因为那样才好看。
令k首先等于j+i,即第一部分的总长度。然后式子变为\(\sum_{i=1}^{n}\sum_{k=i}^{n}C_{k-1}^{i-1}*(m-1)^{k-i}*m^{n-k+i}\)。
然后还是不好看,\(k-1\)变成\(k\),\(i-1\)变成\(i\)。
式子变为\(\sum_{i=0}^{n-1}\sum_{k=i}^{n-1}C_{k}^{i}*(m-1)^{k-i}*m^{n-k+i}\)
换限,\(\sum_{k=0}^{n-1}*\sum_{i=0}^{k}*C_{k}^{i}*(m-1)^{k-i}*m^i*m^{n-k}\)
然后根据二项式定理,我们注意到\(C_{k}^{i}*(m-1)^{k-i}*m^i\)其实就是\((m+m-1)^k\)
所以原式化为\(\sum_{k=0}^{n-1}(2m-1)^k*m^{n-k}\)
然后我们就能很快的求出来了。
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int mod=1e9+7;
void solve(){
int n,m;cin>>n>>m;
vector<ll>a(n+1);vector<ll>b(n+1);
a[0]=1,b[0]=1;
ll ans=0;
for(int i=1;i<=n;i++){
a[i]=a[i-1]*(2ll*m-1ll)%mod;
b[i]=b[i-1]*m%mod;
}
for(int i=0;i<n;i++)ans=(ans+(a[i]*b[n-i]%mod)%mod);
cout<<(ans+b[n])%mod<<"\n";
}
signed main(){
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
srand((unsigned)time(NULL));
//int t;std::cin>>t;while(t--)
solve();
}
标签:Different,Subsets,sum,pos,len,Tuples,然后,序列,我们
From: https://www.cnblogs.com/shi5/p/18050319