\(\text{Problem}:\)Different Subsets For All Tuples
\(\text{Solution}:\)
考虑一个长度为 \(k\) 的子序列,下标为 \(p_{1},p_{2},...,p_{k}\)。设 \(p_{0}=0\),对于相同子序列中字典序最小的 \(p\),有:
即不在子序列中且在 \(p_{k}\) 前的 \(p_{k}-k\) 个位置有 \((m-1)\) 种选法,剩下 \(n-p_{k}+k\) 个位置有 \(m\) 种选法。故答案为:
时间复杂度 \(O(n)\)。
\(\text{Code}:\)
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=1000010, Mod=1e9+7;
inline int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n,m,pw[N+5];
signed main()
{
n=read(), m=read();
pw[0]=1;
for(ri int i=1;i<=n;i++) pw[i]=1ll*pw[i-1]*m%Mod;
int ans=pw[n];
for(ri int i=1,now=1;i<=n;i++)
{
ans=(ans+1ll*pw[n-i+1]*now%Mod)%Mod;
now=1ll*now*(m*2-1)%Mod;
}
printf("%d\n",ans);
return 0;
}
[CF660E] Different Subsets For All Tuples
原文:https://www.cnblogs.com/zkdxl/p/14710798.html