Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- #include <math.h>
- #include <stdlib.h>
- //https://atcoder.jp/contests/abc145/tasks/abc145_d
- long int modo = 1000000007;
- long int binNewt(long int N,long int n1){
- if(n1 == 0)
- return 1;
- long int i, j, iMin = N - n1, jMin = 0, *C;
- C = malloc((n1 + 1) * sizeof(long int));
- C[0] = 1;
- for (i = 1; i <= n1; i++){
- C[i] = 1;
- for (j = i - 1; j > 0; j--){
- C[j] = C[j - 1] + C[j];
- if(C[j] > modo)
- C[j] -= modo;
- }
- }
- for (i = n1 + 1; i <= iMin; i++)
- for (j = n1; j > 0; j--){
- C[j] = (C[j - 1] + C[j]);
- if(C[j] > modo)
- C[j] -= modo;
- }
- for (i = iMin + 1; i < N; i++){
- for (j = n1; j > jMin; j--){
- C[j] = (C[j - 1] + C[j]);
- if(C[j] > modo)
- C[j] -= modo;
- }
- jMin++;
- }
- return (C[n1] + C[n1 - 1]) % modo;
- }
- int main() {
- long int x, y, n1, N;
- scanf("%ld %ld\n", &x, &y);
- n1 = (x < y) ? (2 * x - y) / 3 : (2 * y - x) / 3;
- N = y + x;
- if((N % 3 != 0) || n1 < 0 || n1 > N)
- printf("0\n");
- else{
- N /= 3;
- printf("%ld\n", binNewt(N, n1));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement