题意：
解法：
先画图，根据每个位置的方案数找找规律： 发现是杨辉三角： 1 11 121 1331 …
杨辉三角
:(下标从
0开始
)
第
0层x
+y
=0,
第
1层x
+y
=3,
第
2层x
+y
=6,
...
显然层数t
=(x
+y
)/3,如果
(x
+y
)%3!=0说明无法到达
(x
,y
),答案为
0.
现在要计算
(x
,y
)是这一层的第几个
.
第t层的第一个
:(t
*2,t
),
而且同一层的横纵坐标只相差
1,
那么
(x
,y
)是第y
-t个
,答案为
C(t
,y
-t
)
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
const int maxm
=1e6+5;
const int mod
=1e9+7;
int fac
[maxm
],inv
[maxm
];
int x
,y
;
int C(int n
,int m
){
if(m
>n
||m
<0)return 0;
return fac
[n
]*inv
[m
]%mod
*inv
[n
-m
]%mod
;
}
int ppow(int a
,int b
,int mod
){
int ans
=1%mod
;a
%=mod
;
while(b
){
if(b
&1)ans
=ans
*a
%mod
;
a
=a
*a
%mod
;
b
>>=1;
}
return ans
;
}
void init(){
fac
[0]=1;
for(int i
=1;i
<maxm
;i
++)fac
[i
]=fac
[i
-1]*i
%mod
;
inv
[maxm
-1]=ppow(fac
[maxm
-1],mod
-2,mod
);
for(int i
=maxm
-2;i
>=0;i
--)inv
[i
]=(i
+1)*inv
[i
+1]%mod
;
}
signed main(){
init();
cin
>>x
>>y
;
if((x
+y
)%3){
cout
<<0<<endl
;
}else{
int t
=(x
+y
)/3;
int p
=y
-t
;
int ans
=C(t
,p
);
cout
<<ans
<<endl
;
}
return 0;
}
