Submission #19955

#	Time	Username	Problem	Language	Result	Execution time	Memory
19955		xdoju	카드 (kriii4_Z)	C++14	0 / 100	10 ms	36284 KiB

Z

#include <cstdio>
using namespace std;

const int MOD = 1000000007;

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

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

inline int modprod(int a, int b) {
	a = a % MOD;
	b = b % MOD;
	return ((long long)a * b) % MOD;
}

inline int modprod(int a, int b, int c) {
	c = c % MOD;
	return (modprod(a, b) * (long long)c) % MOD;
}

inline int moddiv(int a, int b) {
	return ((long long)a * modinv(b)) % MOD;
}

int n, l, existCnt = 0;
int d[3001];
int fact[3001];
int c[3001][3001];

void proc() {
	scanf("%d %d", &n, &l);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &d[i]);
		existCnt += (d[i] > 0) ? 1 : 0;
	}

	c[1][0] = c[1][1] = 1;
	for (int i = 2; i <= n; ++i) {
		c[i][0] = c[i][i] = 1;
		for (int j = 1; j < i; ++j) {
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
		}
	}
	fact[0] = fact[1] = 1;
	for (int i = 2; i <= n; ++i) {
		fact[i] = modprod(fact[i - 1], i);
	}

	int ans = 0;
	for (int k = existCnt; k <= n; ++k) {
		if (k > l) {
			break;
		}

		int u = moddiv(1, modpow(n, k));
		int v = modprod(u, fact[k]);

		int w = moddiv(modpow(k, l - k), modpow(n, l - k));

		int x = modprod(v, w);

		ans = (ans + x) % MOD;
	}
	printf("%d", ans);
}

int main() {
	//freopen("input.txt", "r", stdin);
	proc();
	return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 87