Submission #1393119


Source Code Expand

/*{{{*/
#include <bits/stdc++.h>
using namespace std;

#define rep(i, x, y) for(int i = (x), _ = (y); i <= _; ++ i)
#define per(i, x, y) for(int i = (x), _ = (y); i >= _; -- i)
#define dprintf(...) fprintf(stderr, __VA_ARGS__)
#define disp(x) cout << #x << " = " << x << "; "

typedef long long LL;

template <class T> bool chkmin(T& a, T b) { return a > b ? a = b, true : false; }
template <class T> bool chkmax(T& a, T b) { return a < b ? a = b, true : false; }

template <class T> void read(T& a) {
	char c = getchar(); 
	T f = 1; 
	a = 0;
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) a = a * 10 + c - '0';
	a *= f;
}
/*}}}*/

const int maxN = 1e5 + 5, mo = 1e9 + 7;

int pow_mod(int x, int t)
{
	int ret = 1;
	while(t)
	{
		if(t & 1) ret = (LL) ret * x % mo;
		x = (LL) x * x % mo; t >>= 1;
	}
	return ret;
}

int N;
int A, B;
int a[maxN];
int fac[maxN];
int cnt[maxN];
int lala;

int C(int n, int m)
{
	if(n < m) return 0;
	return (LL) fac[n] * pow_mod(fac[m], mo - 2) % mo * pow_mod(fac[n - m], mo - 2) % mo;
}

int main()
{
#ifdef Leeson
	freopen("tmp.in", "r", stdin);
	freopen("tmp.out", "w", stdout);
#endif

	fac[0] = 1;
	rep(i, 1, 100001) fac[i] = (LL) fac[i - 1] * i % mo;
	read(N);
	rep(i, 1, N + 1)
	{
		read(a[i]);
		if((++cnt[a[i]]) == 2)
		{
			lala = a[i];
			break;
		}
	}
	rep(i, 1, N + 1) if(a[i] == lala)
	{
		A = i - 1;
		break;
	}
	per(i, N + 1, 1) if(a[i] == lala)
	{
		B = N + 1 - i;
		break;
	}
	rep(i, 1, N + 1)
	{
		int ans = (C(N + 1, i) - C(A + B, i - 1) + mo) % mo;
		printf("%d\n", ans);
	}

	return 0;
}

Submission Info

Submission Time
Task D - 11
User leeson
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1671 Byte
Status AC
Exec Time 75 ms
Memory 2432 KiB

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 75 ms 2048 KiB
mx.txt AC 48 ms 2432 KiB
rnd_0.txt AC 56 ms 2048 KiB
rnd_1.txt AC 41 ms 1792 KiB
rnd_2.txt AC 17 ms 1024 KiB
rnd_3.txt AC 14 ms 896 KiB
rnd_4.txt AC 17 ms 1152 KiB
sample1.txt AC 2 ms 640 KiB
sample2.txt AC 2 ms 640 KiB
sample3.txt AC 2 ms 640 KiB