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
AC × 2
RE × 1
AC × 9
RE × 1
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