Submission #3015546
Source Code Expand
N,A,B,K = map(int,input().split()) sprime = 998244353 # approx 10**9 A,B = sorted((A,B)) if (A+B) * N < K: print(0) exit() def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m memo = [0] * (N+1) memo[0] = memo[N] = 1 for i in range(1,N//2+1): v = memo[i-1] * (N-i+1) * modinv(i,sprime) v = v % sprime memo[i] = memo[N-i] = v # max is A*N + B*N sum = 0 for b in range(N+1): a = (K-b*B)//A if 0 <= a <= N and a*A+b*B == K: sum += memo[a]*memo[b] sum %= sprime print(sum)
Submission Info
Submission Time | |
---|---|
Task | B - RGB Coloring |
User | DanGo |
Language | Python (3.4.3) |
Score | 700 |
Code Size | 764 Byte |
Status | AC |
Exec Time | 880 ms |
Memory | 10128 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 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 | 762 ms | 10128 KB |
in02.txt | AC | 767 ms | 10128 KB |
in03.txt | AC | 750 ms | 10128 KB |
in04.txt | AC | 793 ms | 10128 KB |
in05.txt | AC | 743 ms | 10128 KB |
in06.txt | AC | 793 ms | 10128 KB |
in07.txt | AC | 784 ms | 10128 KB |
in08.txt | AC | 229 ms | 5160 KB |
in09.txt | AC | 772 ms | 9872 KB |
in10.txt | AC | 584 ms | 8420 KB |
in11.txt | AC | 649 ms | 8872 KB |
in12.txt | AC | 274 ms | 5504 KB |
in13.txt | AC | 461 ms | 7292 KB |
in14.txt | AC | 127 ms | 4128 KB |
in15.txt | AC | 251 ms | 5284 KB |
in16.txt | AC | 88 ms | 3744 KB |
in17.txt | AC | 539 ms | 7740 KB |
in18.txt | AC | 786 ms | 10108 KB |
in19.txt | AC | 880 ms | 10108 KB |
in20.txt | AC | 856 ms | 10108 KB |
in21.txt | AC | 18 ms | 3064 KB |
sample01.txt | AC | 18 ms | 3064 KB |
sample02.txt | AC | 18 ms | 3064 KB |
sample03.txt | AC | 226 ms | 5160 KB |