Submission #3919723


Source Code Expand

Copy
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

const int N_MAX = 100010;
ll Per[N_MAX] = {}; // n!
ll Per_inv[N_MAX] = {}; //(n!)^-1

ll nCr(ll n, ll r){
    if(n<r) return 0;

    if (n == r || r == 0)
        return 1;
    else
        return Per[n] * Per_inv[n-r] % mod * Per_inv[r] % mod;  
}

// a^b mod p
ll mod_pow(ll a, ll b){
    if(b==0) return 1;

    // 肩が奇数
    if(b%2==1){
        return a * mod_pow(a, b-1) % mod;
    }
    else{
        return mod_pow(a*a % mod, b/2) % mod;
    }
}

vector<ll> A;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    int N;
    cin >> N;

    A.resize(N+1);
    FOR(i, 0, N+1){
        cin >> A.at(i);
    }

    // 重複探し
    map<ll, int> mp;
    for(ll a : A){
        mp[a]++;
    }

    int dup_val;
    for(auto p : mp){
        if(p.second == 2){
            dup_val = p.first;
        }
    }

    int left = -1;
    int right = -1;
    FOR(i, 0, N+1){
        if(A[i]==dup_val){
            if(left==-1){
                left = i;
            }else{
                right = i;
            }
        }
    }

    // nCr高速化準備
    Per[1] = 1;
    FOR(i, 2, N_MAX){
        Per[i] = i * Per[i-1] % mod;
    }

    Per_inv[1] = 1;
    FOR(i, 2, N_MAX){
        Per_inv[i] = mod_pow(Per[i], 1000000005);
    }

    FOR(k, 1, N+2){
        ll all = nCr(N+1, k);
        ll dup = nCr(N - right + left, k-1);
        ll a = all - dup;
        if(a<0){
            a+=mod;
        }
        p(a%mod);
    }
        
    return 0;
}

Submission Info

Submission Time
Task D - 11
User peroon
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2196 Byte
Status AC
Exec Time 235 ms
Memory 9856 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 234 ms 9856 KB
mx.txt AC 235 ms 9856 KB
rnd_0.txt AC 200 ms 8320 KB
rnd_1.txt AC 173 ms 7424 KB
rnd_2.txt AC 70 ms 3328 KB
rnd_3.txt AC 65 ms 3200 KB
rnd_4.txt AC 90 ms 4224 KB
sample1.txt AC 33 ms 1792 KB
sample2.txt AC 33 ms 1792 KB
sample3.txt AC 33 ms 1792 KB