Submission #19668

#	Time	Username	Problem	Language	Result	Execution time	Memory
19668		xdoju	비트 (kriii4_Q)	C++14	9 / 100	0 ms	1088 KiB

Q

#include <cstdio>
using namespace std;

const long long MOD = 1000000007ll;

long long modpow(long long r, long long n) {
	long long ret = 1;
	while (n > 0) {
		if (n % 2 > 0) {
			ret = (ret * r) % MOD;
		}
		r = (r * r) % MOD;
		n /= 2;
	}
	return ret;
}

long long modinv(long long n) {
	return modpow(n, MOD - 2);
}

long long coff[300], add[300];
long long ans[300];

void proc() {
	int n, k;
	scanf("%d %d", &n, &k);

	coff[1] = ((n - 1) * modinv(n)) % MOD;
	add[1] = 1;
	for (int i = 2; i < n; ++i) {
		long long t = (((coff[i - 1] * i) % MOD) * modinv(n)) % MOD;
		long long u = (1 - t + MOD) % MOD;

		long long v = ((n - i) * modinv(n)) % MOD;
		coff[i] = (v * modinv(u)) % MOD;

		long long w = (1 + ((((i * modinv(n)) % MOD) * add[i - 1]) % MOD)) % MOD;
		add[i] = (w * modinv(u)) % MOD;
	}

	ans[n] = ((add[n - 1] + 1) * modinv((1 - coff[n - 1] + MOD) % MOD)) % MOD;
	for (int i = n - 1; i >= 1; --i) {
		ans[i] = (((ans[i + 1] * coff[i]) % MOD) + add[i]) % MOD;
	}

	for (int i = 1; i <= n; ++i) {
		printf("%lld\n", ans[i]);
	}
}

int main() {
	proc();
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 91