Submission #2232908
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define MOD ll(1e9+7) #define MAX_N 100005 ll factorial[MAX_N]; int cnt[MAX_N]; void make_factorial_tableMOD(){ factorial[0] = 1; for(int i = 1; i < MAX_N; i++){ factorial[i] = factorial[i-1]*i%MOD; } } ll bisection_powerMOD(ll x,ll y){ if(y==0) { return 1; } ll t = bisection_powerMOD(x*x%MOD,y/2); if(y%2==1) { t = t*x%MOD; } return t; } ll nCrMOD(int n, int r){ if(r<0){return 1;} ll a = factorial[n]; ll b = a*bisection_powerMOD(factorial[r],(MOD-2))%MOD; ll c = b*bisection_powerMOD(factorial[n-r],MOD-2)%MOD; return c % MOD; } int main(){ int n, a; cin >> n; int l, r, lo, ro; for(int i = 0; i < MAX_N; i++){ cnt[i] = -1; } for(int i = 0; i < n+1; i++){ cin >> a; if(cnt[a]==-1){cnt[a] = i;} else{l = cnt[a]; r = i;} } lo = l; ro = n - r; make_factorial_tableMOD(); ll u, v; for(int i = 0; i < n+1; i++){ u = nCrMOD(n+1,i+1); v = lo + ro >= i ? nCrMOD(lo+ro,i) : 0LL; cout << (u - v + MOD)%MOD << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 11 |
User | kujira438x |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1257 Byte |
Status | AC |
Exec Time | 281 ms |
Memory | 2432 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt |
All | 1.txt, mx.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
1.txt | AC | 281 ms | 2432 KB |
mx.txt | AC | 240 ms | 2432 KB |
rnd_0.txt | AC | 217 ms | 2176 KB |
rnd_1.txt | AC | 176 ms | 2048 KB |
rnd_2.txt | AC | 56 ms | 1664 KB |
rnd_3.txt | AC | 48 ms | 1536 KB |
rnd_4.txt | AC | 74 ms | 1664 KB |
sample1.txt | AC | 2 ms | 1408 KB |
sample2.txt | AC | 2 ms | 1408 KB |
sample3.txt | AC | 2 ms | 1408 KB |