问题 C: 11
时间限制: 1 Sec 内存限制: 128 MB题目描述
You are given an integer sequence of length n+1, a1,a2,…,an+1, which consists of the n integers 1,…,n. It is known that each of the n integers 1,…,n appears at least once in this sequence.
For each integer k=1,…,n+1, find the number of the different subsequences (not necessarily contiguous) of the given sequence with length k, modulo 109+7.
Notes
If the contents of two subsequences are the same, they are not separately counted even if they originate from different positions in the original sequence.
A subsequence of a sequence a with length k is a sequence obtained by selecting k of the elements of a and arranging them without changing their relative order. For example, the sequences 1,3,5 and 1,2,3 are subsequences of 1,2,3,4,5, while 3,1,2 and 1,10,100 are not.
Constraints
1≤n≤105
1≤ai≤n
Each of the integers 1,…,n appears in the sequence.
n and ai are integers.
For each integer k=1,…,n+1, find the number of the different subsequences (not necessarily contiguous) of the given sequence with length k, modulo 109+7.
Notes
If the contents of two subsequences are the same, they are not separately counted even if they originate from different positions in the original sequence.
A subsequence of a sequence a with length k is a sequence obtained by selecting k of the elements of a and arranging them without changing their relative order. For example, the sequences 1,3,5 and 1,2,3 are subsequences of 1,2,3,4,5, while 3,1,2 and 1,10,100 are not.
Constraints
1≤n≤105
1≤ai≤n
Each of the integers 1,…,n appears in the sequence.
n and ai are integers.
输入
Input is given from Standard Input in the following format:
n
a1 a2 ... an+1
n
a1 a2 ... an+1
输出
Print n+1 lines. The k-th line should contain the number of the different subsequences of the given sequence with length k, modulo 109+7.
样例输入
3
1 2 1 3
样例输出
3
5
4
1
提示
There are three subsequences with length 1: 1 and 2 and 3.
There are five subsequences with length 2: 1,1 and 1,2 and 1,3 and 2,1 and 2,3.
There are four subsequences with length 3: 1,1,3 and 1,2,1 and 1,2,3 and 2,1,3.
There is one subsequence with length 4: 1,2,1,3.
题意：
给你一个数 n, 序列长度为 n + 1, 保证序列中至少有 1 - n 中所有数，即某个数出现过两次，从该序列中按顺序拿 1 - > n+1个的方案
题解：
从n + 1中拿i 个 是 C(n+1,i),但对于出现两次的数，会出现重复，若出现两次的数的位置是 l 和 r，在拿了一个出现两次的那个数，对于从 l - r 区间外选取，会出现重复，即总的减去重复的就是答案。 C(n + 1,i) - C(n + 1 - (r - l + 1),i - 1)
求一下组合数，加逆元 该题就解决了
code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int N = 1e5+10; int vis[N]; ll inv(ll b){ return b==1||b==0?1:(mod-mod/b)*inv(mod%b)%mod; } ll f[N]; ll C(ll n,ll m) { if(n<m) return 0; return f[n]*inv(f[m])%mod*inv(f[n-m])%mod; } void init() { f[0]=1; for(int i=1;i<N;i++) f[i]=f[i-1]*i%mod; } int main() { int n,first,last,dig; init(); memset(vis,0,sizeof(vis)); scanf("%d",&n); for(int i = 1;i <= n+1;i++) { scanf("%d",&dig); if(vis[dig]) first = vis[dig],last = i; else vis[dig] = i; } for(int i = 1;i <= n+1;i++) { //cout<<C(n+1,i)<<" "<<C(n+1 - (last - first),i - 1)<<endl; printf("%lld ", (C(n+1,i) - C(n + 1 - (last - first + 1),i-1) + mod)%mod); } return 0; }