Submission #3018169


Source Code Expand

#include<iostream>

#include <vector>
#include <list>
#include<stack>
#include<queue>
#include<array>

#include <set>
#include<map>

#include<string>
#include<stdlib.h>

#include<algorithm>
#include <functional>
#include<math.h>

#include<fstream>
#include<iomanip>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 998244353;// 10^9+7
constexpr ll LIM = 300'000;

//変数
ll N, A, B, K;




//繰り返し累乗法
//in:  x,n,mod
//out: x^n(Mod mod)
template<typename T>
T mod_pow(T x, T n, T mod) {
	T res = 1;
	while (n > 0) {
		if (n & 1)res = (res * x) % mod;
		x = (x * x) % mod;
		n >>= 1;
	}
	return res;
}

//
vector<ll> fact, inv;
void make_contents()
{
	ll tmp = 1;
	fact.push_back(0);
	FOR(i, 1, LIM) {
		tmp *= i;
		tmp %= MOD;
		fact.push_back(tmp);
	}

	tmp = mod_pow(tmp, MOD - 2, MOD);
	//inv.push_back(tmp);
	for (ll i = LIM - 1; i > 0; i--) {
		tmp *= i;
		tmp %= MOD;
		inv.push_back(tmp);
	}
	reverse(inv.begin(), inv.end());
	fact[0] = inv[0] = 1;
	/*正当性確認
	REP(i, LIM) {
	cerr << (fact[i] * inv[i]) % MOD << endl;
	}
	*/
}

ll comb(ll n, ll k) {
	ll res = fact[n];
	res *= inv[k]; res %= MOD;
	res *= inv[n - k]; res %= MOD;
	return res;
}





//サブ関数
//入力
void input()
{
	cin >> N >> A >> B >> K;
	make_contents();
}


//計算
void calc()
{
	ll res = 0;
	REP(numA, N + 1) {
		ll will = K - A * numA;
		if (will%B != 0)continue;
		will /= B;
		if (will > N)continue;

		ll tmp = comb(N, numA)*comb(N, will);
		tmp %= MOD;
		res += tmp;
		res %= MOD;
	}
	cout << res << endl;
}


//出力
void output()
{

}


//デバッグ
void debug()
{
	int N;
	cin>>N;
}


//メイン関数
int main()
{
	input();
	calc();
	output();
	debug();
	
	return 0;
}

Submission Info

Submission Time
Task B - RGB Coloring
User toma25
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2134 Byte
Status RE
Exec Time 108 ms
Memory 12524 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 3
AC × 11
WA × 7
RE × 9
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt
All 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 RE 108 ms 12524 KB
in02.txt WA 12 ms 8812 KB
in03.txt RE 106 ms 11500 KB
in04.txt WA 13 ms 11884 KB
in05.txt WA 13 ms 11372 KB
in06.txt RE 106 ms 11116 KB
in07.txt RE 106 ms 8812 KB
in08.txt AC 10 ms 8940 KB
in09.txt AC 12 ms 8940 KB
in10.txt AC 11 ms 9836 KB
in11.txt RE 107 ms 12524 KB
in12.txt AC 11 ms 11244 KB
in13.txt RE 107 ms 10988 KB
in14.txt AC 10 ms 9196 KB
in15.txt RE 105 ms 9580 KB
in16.txt RE 105 ms 12396 KB
in17.txt RE 108 ms 11884 KB
in18.txt WA 14 ms 12396 KB
in19.txt WA 16 ms 11756 KB
in20.txt WA 15 ms 10092 KB
in21.txt WA 10 ms 11244 KB
sample01.txt AC 10 ms 12140 KB
sample02.txt AC 9 ms 9708 KB
sample03.txt AC 11 ms 11628 KB