Submission #2612535
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define NDEBUG
#ifdef DEBUG
#include "cout11.h"
#undef NDEBUG
#endif
#include <cassert>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
#define sz(a) int((a).size())
#define pb push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n) for(int var=0;var<(n);++var)
#define rep1(var,n) for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n) for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define tr(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e) ((s).find(e)!=(s).end())
#define mset(arr,val) memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }
const ll M=998244353LL;
ll ADD(ll x, ll y) { return (x+y) % M; }
ll SUB(ll x, ll y) { return (x-y+M) % M; }
ll MUL(ll x, ll y) { return x*y % M; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { assert(y%M!=0); return MUL(x, POW(y, M-2)); }
ll comb(ll n, ll k) { ll v=1; for(ll i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }
// ax+by=gcd(a,b) を満たすx,yを1組求めたい時に
ll extgcd(ll a, ll b, ll &x, ll &y, ll c=1, ll d=0, ll e=0, ll f=1) {
if (b == 0) {
x = c; y = e; // dot([c,d; e,f], [1;0])
return a;
}
ll q = a/b, r = a%b;
return extgcd(b, r, x, y, d, c-q*d, f, e-q*f); // dot([c,d; e,f], [0,1; 1,-q])
}
pair<ll,ll> abc(ll a, ll b, ll c){
// ax + by = c
ll g = gcd(gcd(a,b),c);
a /= g; b /= g; c /= g;
ll x, y;
extgcd(a,b,x,y);
x *= c, y *= c;
#ifdef DEBUG
// printf("%lldx + %lldy = %lld -> (x=%lld, y=%lld)\n", a*g,b*g,c*g, x,y);
#endif
return make_pair(x, y);
}
int N, A, B;
ll K;
ll fact[300001];
ll pat(ll r, ll g, ll b, ll n){
if (r<0 || g<0 || b<0) return 0;
ll n_ = fact[N];
// ll rgb_ = MUL(MUL(fact[r], fact[g]), fact[b]);
ll rgb_ = MUL(MUL(fact[r], fact[g]),
MUL(fact[b], fact[N-r-g-b]));
return DIV(n_, rgb_);
}
ll solve() {
// Ax + By = K な x,yを求める
ll gab = gcd(A,B);
ll a_ = A / gab, b_ = B / gab;
pair<ll,ll> xy = abc(A,B,K);
ll x = xy.first, y = xy.second;
if (y < 0) {
ll dy = -y / a_;
y += a_ * dy;
x -= b_ * dy;
if (y < 0) { y += a_; x -= b_; }
}
if (x < 0) {
ll dx = -x / b_;
x += b_ * dx;
y -= a_ * dx;
if (x < 0) { x += b_; y -= a_; }
}
if (x < 0 || y < 0) return 0;
// y>=0, x>= 0
ll ans = 0;
for (ll xi=x,yi=y; xi>=0 && yi<=K; ) {
// printf("(%lld, %lld)\n", xi, yi);
ans = ADD(ans, MUL(comb(N, xi), comb(N,yi)));
xi -= b_; yi += a_;
}
for (ll xi=x+b_, yi=y-a_; xi<=K && yi>=0; ) {
// printf("(%lld, %lld)\n", xi, yi);
ans = ADD(ans, MUL(comb(N, xi), comb(N,yi)));
xi += b_; yi -= a_;
}
return ans;
}
int main() {
fact[0] = fact[1] = 1LL;
for (ll i=2; i<=300000; ++i) {
fact[i] = MUL(fact[i-1], i);
}
cin >> N >> A >> B >> K;
cout << solve() << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - RGB Coloring |
User |
naoya_t |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3623 Byte |
Status |
TLE |
Exec Time |
2104 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 |
693 ms |
2560 KB |
in02.txt |
TLE |
2104 ms |
2560 KB |
in03.txt |
AC |
154 ms |
2560 KB |
in04.txt |
AC |
1310 ms |
2560 KB |
in05.txt |
AC |
526 ms |
2560 KB |
in06.txt |
AC |
185 ms |
2560 KB |
in07.txt |
AC |
1339 ms |
2560 KB |
in08.txt |
AC |
800 ms |
2560 KB |
in09.txt |
AC |
592 ms |
2560 KB |
in10.txt |
AC |
36 ms |
2560 KB |
in11.txt |
AC |
83 ms |
2560 KB |
in12.txt |
AC |
14 ms |
2560 KB |
in13.txt |
TLE |
2103 ms |
2560 KB |
in14.txt |
TLE |
2103 ms |
2560 KB |
in15.txt |
TLE |
2104 ms |
2560 KB |
in16.txt |
TLE |
2104 ms |
2560 KB |
in17.txt |
TLE |
2103 ms |
2560 KB |
in18.txt |
TLE |
2104 ms |
2560 KB |
in19.txt |
TLE |
2104 ms |
2560 KB |
in20.txt |
TLE |
2104 ms |
2560 KB |
in21.txt |
AC |
3 ms |
2560 KB |
sample01.txt |
AC |
3 ms |
2560 KB |
sample02.txt |
AC |
3 ms |
2560 KB |
sample03.txt |
AC |
43 ms |
2560 KB |