Submission #2607182

Source Code Expand

Copy
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
//#include <unordered_map>
//#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")

using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()

//typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18; // segment tree size
const ll MOD = 998244353;
const int INF = 0x3f3f3f3f; // memset(dp, 0x3f, sizeof(dp)), 2*INF < INT_MAX
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10; // double EPS

ll mul_inv(ll a, ll b = MOD) {
	ll t1 = a, t2 = b, t3;
	ll v1 = 1, v2 = 0, v3;
	while (t2 != 1) {
		ll x = t1 / t2;
		t3 = t1 - x*t2;
		v3 = v1 - x*v2;
		t1 = t2, t2 = t3;
		v1 = v2, v2 = v3;
	}
	return (v2 + b) % b;
}
ll F[300050];
ll Finv[300050];
ll Co(ll a, ll b) {
	ll rv = F[a] * Finv[b] % MOD;
	return rv * Finv[a - b] % MOD;
}
int main() {
	ll N, A, B, K, i;
	scanf("%lld %lld %lld %lld", &N, &A, &B, &K);

	F[0] = 1;
	for (i = 1; i <= 300000; i++) F[i] = F[i - 1] * i % MOD;
	for (i = 0; i <= 300000; i++) Finv[i] = mul_inv(F[i]);

	ll ans = 0;
	for (i = 0; i <= N; i++) {
		ll c = K - A * i;
		if (c < 0 || c % B) continue;
		ll v = c / B;
		if (v < 0 || v > N) continue;

		ll a = Co(N, i) * Co(N, v) % MOD;
		ans = (ans + a) % MOD;
	}
	return !printf("%lld\n", ans);
}

Submission Info

Submission Time
Task B - RGB Coloring
User dotorya
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1889 Byte
Status
Exec Time 95 ms
Memory 4992 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:67:46: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld", &N, &A, &B, &K);
                                              ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample01.txt, sample02.txt, sample03.txt
All 700 / 700 sample01.txt, sample02.txt, sample03.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, sample01.txt, sample02.txt, sample03.txt
Case Name Status Exec Time Memory
in01.txt 92 ms 4992 KB
in02.txt 92 ms 4992 KB
in03.txt 91 ms 4992 KB
in04.txt 92 ms 4992 KB
in05.txt 92 ms 4992 KB
in06.txt 90 ms 4992 KB
in07.txt 92 ms 4992 KB
in08.txt 90 ms 4992 KB
in09.txt 92 ms 4992 KB
in10.txt 91 ms 4992 KB
in11.txt 91 ms 4992 KB
in12.txt 90 ms 4992 KB
in13.txt 90 ms 4992 KB
in14.txt 90 ms 4992 KB
in15.txt 90 ms 4992 KB
in16.txt 89 ms 4992 KB
in17.txt 91 ms 4992 KB
in18.txt 93 ms 4992 KB
in19.txt 95 ms 4992 KB
in20.txt 95 ms 4992 KB
in21.txt 89 ms 4992 KB
sample01.txt 89 ms 4992 KB
sample02.txt 89 ms 4992 KB
sample03.txt 90 ms 4992 KB