提出 #32446296


ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5000005, mod = 998244353;
int n, a, b, c;
int fac[N], inv[N];
int ans;

int qpow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = 1ll * res * x % mod;
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return res;
}

void init(int maxn) {
	fac[0] = 1;
	for (int i = 1; i <= maxn; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[maxn] = qpow(fac[maxn], mod - 2);
	for (int i = maxn - 1; ~i; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}

int C(int n, int m) {
	if (n < 0 || m < 0 || n < m) return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

void add(int &a, int b) {
	a += b;
	if (a >= mod) a -= mod;
	if (a < 0) a += mod;
}

void mul(int &a, int b) {
	a = 1ll * a * b % mod;
}

int main() {
	scanf("%d%d%d%d", &n, &a, &b, &c);
	init(5000000);
	for (int i = 0; i <= n; ++i) {
		//枚举有i行空着,然后容斥:g(0)=(-1)^i*f(i),i=0~n
		int x = C(n, i);
		int tmp1 = 0, tmp2 = 0, tmp3 = 0;
		for (int j = 0; j <= a; ++j) add(tmp1, C(n - i, j));
		for (int j = 0; j <= b; ++j) add(tmp2, C(n - i, j));
		for (int j = 0; j <= c; ++j) add(tmp3, C(n - i, j));
		mul(x, tmp1), mul(x, tmp2), mul(x, tmp3);
		if (i & 1) add(ans, -x);
		else add(ans, x);
	}
	printf("%d", ans);
	return 0;
}

提出情報

提出日時
問題 G - Gardens
ユーザ Kobe303
言語 C++ (GCC 9.2.1)
得点 0
コード長 1346 Byte
結果 TLE
実行時間 3309 ms
メモリ 42892 KiB

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:42:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   42 |  scanf("%d%d%d%d", &n, &a, &b, &c);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 600
結果
AC × 4
TLE × 1
AC × 18
TLE × 20
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 01_small_00.txt, 01_small_01.txt, 01_small_02.txt, 01_small_03.txt, 01_small_04.txt, 01_small_05.txt, 01_small_06.txt, 01_small_07.txt, 01_small_08.txt, 01_small_09.txt, 01_small_10.txt, 01_small_11.txt, 02_max_00.txt, 02_max_01.txt, 02_max_02.txt, 03_n_max_00.txt, 03_n_max_01.txt, 03_n_max_02.txt, 04_random_00.txt, 04_random_01.txt, 04_random_02.txt, 04_random_03.txt, 04_random_04.txt, 05_zero_00.txt, 05_zero_01.txt, 05_zero_02.txt, 05_zero_03.txt, 06_same_00.txt, 06_same_01.txt, 06_same_02.txt, 07_multinomial_00.txt, 07_multinomial_01.txt, 07_multinomial_02.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 77 ms 42824 KiB
00_sample_01.txt AC 71 ms 42892 KiB
00_sample_02.txt AC 75 ms 42644 KiB
00_sample_03.txt AC 71 ms 42828 KiB
00_sample_04.txt TLE 3309 ms 42292 KiB
01_small_00.txt AC 75 ms 42880 KiB
01_small_01.txt AC 73 ms 42652 KiB
01_small_02.txt AC 73 ms 42876 KiB
01_small_03.txt AC 75 ms 42640 KiB
01_small_04.txt AC 72 ms 42640 KiB
01_small_05.txt AC 71 ms 42696 KiB
01_small_06.txt AC 70 ms 42644 KiB
01_small_07.txt AC 69 ms 42772 KiB
01_small_08.txt AC 73 ms 42768 KiB
01_small_09.txt AC 72 ms 42788 KiB
01_small_10.txt AC 69 ms 42640 KiB
01_small_11.txt AC 70 ms 42764 KiB
02_max_00.txt TLE 3309 ms 42392 KiB
02_max_01.txt TLE 3309 ms 42380 KiB
02_max_02.txt TLE 3309 ms 42448 KiB
03_n_max_00.txt TLE 3309 ms 42380 KiB
03_n_max_01.txt TLE 3309 ms 42384 KiB
03_n_max_02.txt TLE 3309 ms 42336 KiB
04_random_00.txt TLE 3309 ms 42320 KiB
04_random_01.txt TLE 3309 ms 42316 KiB
04_random_02.txt TLE 3309 ms 42364 KiB
04_random_03.txt TLE 3309 ms 42392 KiB
04_random_04.txt TLE 3309 ms 42336 KiB
05_zero_00.txt AC 88 ms 42784 KiB
05_zero_01.txt AC 200 ms 42672 KiB
05_zero_02.txt TLE 3309 ms 42316 KiB
05_zero_03.txt TLE 3309 ms 42452 KiB
06_same_00.txt TLE 3309 ms 42368 KiB
06_same_01.txt TLE 3309 ms 42288 KiB
06_same_02.txt TLE 3309 ms 42316 KiB
07_multinomial_00.txt TLE 3309 ms 42388 KiB
07_multinomial_01.txt TLE 3309 ms 42384 KiB
07_multinomial_02.txt TLE 3309 ms 42516 KiB