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
AC × 3
AC × 10
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