[Codeforces660E]: Different Subsets For All Tuples

2018-04-09Chentiancai_nn?

原题链接 : http://codeforces.com/problemset/problem/660/E

题意

对于长度为$N$、每个元素在$[1..M]$间的所有数列,求其本质不同的子序列个数之和。$N,M≤10^6$。

题解

这道题一开始都不知道自己在想什么,直到被SZB大佬拍醒。
发现因为是所有的序列和所有本质不同的子序列。所以5个1和长度为5的子序列出现的次数是一样的,只要算出一个乘上$m^k$就行了。
对于长为k的子序列,它出现的次数是$$\sum_{i = k}^{n}C^i_n\times(m-1)^{n-i}$$
然后你发现这个东西从后往前算就可以继承上一个,也就是后缀和。
当然空串手动加上(虽然好像并不用?反正我加上了)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
typedef long long ll;
inline ll read(){
ll x = 0,f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}
return x*f;
}

const int N = 1000000,mod = 1e9+7;
int n,m;
int ans,now;
int sum[N+5],rev[N+5];

inline int qpow(int x,int n){
int ans = 1;
for(;n;n >>= 1,x = 1LL*x*x%mod)
if(n&1) ans = 1LL*ans*x%mod;
return ans;
}

inline int C(int n,int m){
return 1LL*sum[n]*rev[m]%mod*rev[n-m]%mod;
}

signed main(){
sum[0] = 1; for(int i = 1;i <= N;++i) sum[i] = 1LL*sum[i-1]*i%mod;
rev[N] = qpow(sum[N],mod-2); for(int i = N;i;--i) rev[i-1] = 1LL*rev[i]*i%mod;
n = read(); m = read();
ans = qpow(m,n);
for(int i = n;i >= 1;--i){ //有几位
now = (now + 1LL*C(n,i)*qpow(m-1,n-i)%mod)%mod;
ans = (ans + 1LL*now*qpow(m,i)%mod)%mod;
}
printf("%d\n", ans);
return 0;
}

检测到你还在使用百度这个搜索引擎,
做为一个程序员,这是一种自暴自弃!

作环保的程序员,从不用百度开始!

Close