Submission #2232666
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; cin >> n; vector<int> a(n+1); 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[i]; if(cnt[a[i]]==-1){cnt[a[i]] = i;} else{l = cnt[a[i]]; 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 << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 11 |
User | kujira438x |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1278 Byte |
Status | WA |
Exec Time | 268 ms |
Memory | 2816 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | WA | 268 ms | 2816 KB |
mx.txt | AC | 222 ms | 2816 KB |
rnd_0.txt | WA | 207 ms | 2560 KB |
rnd_1.txt | WA | 168 ms | 2432 KB |
rnd_2.txt | WA | 54 ms | 1664 KB |
rnd_3.txt | WA | 45 ms | 1664 KB |
rnd_4.txt | WA | 70 ms | 1792 KB |
sample1.txt | AC | 2 ms | 1408 KB |
sample2.txt | AC | 2 ms | 1408 KB |
sample3.txt | AC | 2 ms | 1408 KB |