Submission #3784125
Source Code Expand
#include<iostream> #include<cstring> #include<cstdio> #include<map> #include<set> #include<vector> #include<algorithm> #include<cmath> #include<fstream> #include<iomanip> #include<unordered_set> using namespace std; typedef long long ll; typedef unsigned long long ull; const ll mod = 998244353; const ll N = 3 * 100000 + 5; ll Mode(ll a, ll b){ ll sum = 1; while (b) { if (b & 1) { sum = (sum * a) % mod; b--; } b /= 2; a = a * a % mod; } return sum; } //快速幂取模 ll inv(ll a){ return Mode(a, mod - 2); } //逆元 ll jc[N]; void init() //预处理算阶乘 { jc[0] = 1; for(int i = 1; i < N; ++i) jc[i] = jc[i-1]*i%mod; } ll C(ll n, ll m){ if(n<0||m>n) return 0; return ((jc[n] % mod) * ((inv(jc[m]) * inv(jc[n - m])) % mod)) % mod; }//组合数 int main(){ // ios::sync_with_stdio(false); // ifstream cin("data.txt"); // freopen("data.txt", "r", stdin); init(); ll n, a, b, k; ll ans = 0; cin >> n >> a >> b >> k; if(k == 0){ cout << 1 << endl; return 0; } for(ll i = 1; i <= n; i++){ //cout << "n = " << i << endl; if(!((k - a * i) % b)){ //cout << "jin\n"; ll t1 = i; ll t2 = ((k - a * i) / b); //cout << "t1 = " << t1 << "\nt2 = " << t2 << endl; for(ll z = 0; z <= min(t1, t2); z++){ //cout << "z = " << z << endl; ll x = t1 - z;//cout << "x = " << x << endl; ll y = t2 - z;//cout << "y = " << y << endl; ll m = n - z - x - y;//cout << "m = " << m << endl; if(x < 0 || y <0 || m < 0)continue; ll cnt = C(n, x) % mod; cnt *= C(n - x, y); cnt %= mod; cnt *= C(n - x - y, z); cnt %= mod; cnt *= C(n - x - y - z, m); cnt %= mod; //cout << "cnt = " << cnt << endl; ans += cnt; ans %= mod; } } } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - RGB Coloring |
User | sheeeeeeep |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1875 Byte |
Status | TLE |
Exec Time | 2103 ms |
Memory | 2560 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 700 | ||||||
Status |
|
|
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 | AC | 189 ms | 2560 KB |
in02.txt | TLE | 2103 ms | 2560 KB |
in03.txt | AC | 31 ms | 2560 KB |
in04.txt | AC | 868 ms | 2560 KB |
in05.txt | AC | 45 ms | 2560 KB |
in06.txt | AC | 348 ms | 2560 KB |
in07.txt | AC | 173 ms | 2560 KB |
in08.txt | AC | 24 ms | 2560 KB |
in09.txt | AC | 316 ms | 2560 KB |
in10.txt | AC | 115 ms | 2560 KB |
in11.txt | AC | 150 ms | 2560 KB |
in12.txt | AC | 37 ms | 2560 KB |
in13.txt | TLE | 2103 ms | 2560 KB |
in14.txt | TLE | 2103 ms | 2560 KB |
in15.txt | TLE | 2103 ms | 2560 KB |
in16.txt | TLE | 2103 ms | 2560 KB |
in17.txt | TLE | 2103 ms | 2560 KB |
in18.txt | TLE | 2103 ms | 2560 KB |
in19.txt | TLE | 2103 ms | 2560 KB |
in20.txt | TLE | 2103 ms | 2560 KB |
in21.txt | AC | 4 ms | 2560 KB |
sample01.txt | AC | 4 ms | 2560 KB |
sample02.txt | AC | 4 ms | 2560 KB |
sample03.txt | AC | 52 ms | 2560 KB |