Submission #3786143
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using tii = tuple<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define INF 1E9
#define LINF 1E18*5
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384
template<class S, class T>ostream& operator<<(ostream&os, pair<S, T>p) { os << "[" << p.first << ", " << p.second << "]"; return os; };
template<class S>auto&operator<<(ostream&os, vector<S>t) { bool a = 1; for (auto s : t) { os << (a ? "" : " ") << s; a = 0; } return os; }
//int dx[]={1,1,1,0,-1,-1,-1,0},dy[8]={1,0,-1,-1,-1,0,1,1,1};
//
constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
class compare {
public:
bool operator()(tuple<int, int> a, tuple<int, int> b) {
return (get<1>(a) < get<1>(b));
}
};
vl fact(100002), finv(100002);
ll modpw(ll x, ll k) {
ll res = 1;
while (k != 0) {
if (k & 1) res = res*x % MOD;
x = x*x % MOD;
k = k >> 1;
}
return res;
}
ll comb(ll n, ll k) {
if (n == 0 && k == 0)return 1;
if (n < k || n < 0)return 0;
return fact[n] * finv[n - k] % MOD * finv[k] % MOD;;
}
int main() {
//cin.tie(0);
//ios::sync_with_stdio(false);
ll n, d, fi = -1, se = 0;
cin >> n;
vl v(n), b(n + 1);
fact[0] = 1;
finv[0] = 1;
rep (i,100001) {
fact[i + 1] = (fact[i] * (i + 1)) % MOD;
finv[i + 1] = modpw(fact[i + 1], MOD-2);
}
rep(i, n+1) {
cin >> v[i];
b[v[i]]++;
if (b[v[i]] == 2)d = v[i];
}
rep(i, n+1) {
if (v[i] == d) {
if (fi == -1)fi = i + 1;
else se = i + 1;
}
}
ll tmp = n - se + fi;
rep(i, n + 1) {
ll ans;
ans = comb(n+1,i+1);
if (i >= 0 && i <= tmp)ans = (ans + MOD - comb(tmp, i)) % MOD;
printf("%lld\n", ans);
}
}
Submission Info
Submission Time |
|
Task |
D - 11 |
User |
makecir |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2195 Byte |
Status |
RE |
Exec Time |
117 ms |
Memory |
4352 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 |
AC |
58 ms |
4352 KB |
mx.txt |
AC |
57 ms |
4352 KB |
rnd_0.txt |
AC |
50 ms |
3840 KB |
rnd_1.txt |
AC |
45 ms |
3584 KB |
rnd_2.txt |
AC |
26 ms |
2304 KB |
rnd_3.txt |
AC |
25 ms |
2176 KB |
rnd_4.txt |
AC |
30 ms |
2560 KB |
sample1.txt |
RE |
117 ms |
1792 KB |
sample2.txt |
AC |
18 ms |
1792 KB |
sample3.txt |
AC |
19 ms |
1792 KB |