Submission #1397459
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
ModInt inverse() const {
long long a = x, b = MOD, u = 1, v = 0;
while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
return ModInt(u);
}
bool operator==(ModInt that) const { return x == that.x; }
bool operator!=(ModInt that) const { return x != that.x; }
ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r;
}
template<typename T, int FAC_MAX> struct Comb {
vector<T> fac, ifac;
Comb() {
fac.resize(FAC_MAX, 1); ifac.resize(FAC_MAX, 1); rep(i, 1, FAC_MAX) fac[i] = fac[i - 1] * i;
rep(i, 1, FAC_MAX) ifac[i] = T(1) / fac[i];
}
T aPb(int a, int b) { if (b < 0 || a < b) return T(0); return fac[a] * ifac[a - b]; }
T aCb(int a, int b) { if (b < 0 || a < b) return T(0); return fac[a] * ifac[a - b] * ifac[b]; }
T nHk(int n, int k) {
if (n == 0 && k == 0) return T(1); if (n <= 0 || k < 0) return 0;
return aCb(n + k - 1, k);
}
};
typedef ModInt<1000000007> mint;
/*---------------------------------------------------------------------------------------------------
∧_∧
∧_∧ (´<_` ) Welcome to My Coding Space!
( ´_ゝ`) / ⌒i
/ \ | |
/ / ̄ ̄ ̄ ̄/ |
__(__ニつ/ _/ .| .|____
\/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/
Comb<mint, 201010> com;
int N, A[101010];
int cnt[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> N;
rep(i, 0, N + 1) cin >> A[i];
rep(i, 0, N + 1) cnt[A[i]]++;
int twice = -1;
rep(i, 1, N + 1) if (cnt[i] == 2) twice = i;
int a = -1, b;
rep(i, 0, N + 1) if (A[i] == twice) {
if(a < 0) a = i;
else b = i;
}
printf("%d\n", N);
int cnt = a + (N - b);
rep(i, 2, N + 1) {
mint ans = com.aCb(N + 1, i);
if(i - 1 <= cnt) ans -= com.aCb(cnt, i - 1);
printf("%d\n", ans.get());
}
printf("1\n");
}
Submission Info
Submission Time |
|
Task |
D - 11 |
User |
hamayanhamayan |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
3734 Byte |
Status |
AC |
Exec Time |
82 ms |
Memory |
3584 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 |
82 ms |
3584 KB |
mx.txt |
AC |
81 ms |
3584 KB |
rnd_0.txt |
AC |
78 ms |
3328 KB |
rnd_1.txt |
AC |
76 ms |
3072 KB |
rnd_2.txt |
AC |
67 ms |
2176 KB |
rnd_3.txt |
AC |
67 ms |
2176 KB |
rnd_4.txt |
AC |
69 ms |
2432 KB |
sample1.txt |
AC |
64 ms |
1792 KB |
sample2.txt |
AC |
64 ms |
1792 KB |
sample3.txt |
AC |
64 ms |
1792 KB |