ARC077D 11

发布时间：2020-12-14 04:18:00 所属栏目：大数据来源：网络整理

导读：～～～题面～～～题解：做这道题的时候zz了，，，，写了个很复杂的式子，然而后面重新想就发现很简单了。考虑用总的情况减去重复的。假设唯一重复的两个数的位置分别是l和r，那么唯一会导致重复的方案就是中间不取，只取l和r中的一个和两边的数。那么$

～～～题面～～～

题解：

　　做这道题的时候zz了，，，，

　　写了个很复杂的式子，然而后面重新想就发现很简单了。

　　考虑用总的情况减去重复的。

　　假设唯一重复的两个数的位置分别是l和r，那么唯一会导致重复的方案就是中间不取，只取l和r中的一个和两边的数。

　　那么$ans =binom{k}{n} - binom{}{} binom{k - 1}{n - r + l}$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define R register int
 4 #define AC 100100
 5 #define p 1000000007
 6 #define LL long long
 7 
 8 int n,l,r,k;
 9 LL s[AC],C[AC],inv[AC],Cl[AC];//存下每个数第一次出现的地方
10 
11 int read()
12 {
13     int x = 0;char c = getchar();
14     while(c > ‘9‘ || c < ‘0‘) c = getchar();
15     while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘,c = getchar();
16     return x;
17 }
18 
19 inline void pre()
20 {
21     n = read(),k = n + 1;
22     int x;
23     for(R i = 1; i <= k; i ++)
24     {
25         x = read();
26         if(s[x]){l = s[x],r = i; break;}
27         s[x] = i;
28     }
29 }
30 
31 inline void work()
32 {
33     C[0] = inv[1] = Cl[0] = 1;
34     for(R i = 2; i <= k; i ++) inv[i] = (p - p / i) * inv[p % i] % p; 
35     for(R i = 1; i <= k; i ++) C[i] = C[i - 1] * (k - i + 1) % p * inv[i] % p;
36     for(R i = 1; i <= k; i ++) Cl[i] = Cl[i - 1] * (n - r + l - i + 1) % p * inv[i] % p;
37     printf("%dn",n);
38     for(R i = 2; i <= k; i ++)
39         printf("%lldn",(C[i] - Cl[i - 1] + p) % p);
40 }
41 
42 int main()
43 {
44     //freopen("in.in","r",stdin);
45     pre();
46     work();
47     //fclose(stdin);
48     return 0;
49 }

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!