深搜过不了,这题是递推
by DOCTYPE_OIers @ 2020-08-16 14:36:26
这题不是小学奥数吗(((
by yummy @ 2020-08-16 14:37:16
小奥,标数法(((
by DOCTYPE_OIers @ 2020-08-16 14:38:01
@[DOCTYPE_OIers](/user/222382) 啊这题不是组合数 $O(N+M)$ 搞法吗(((
by yummy @ 2020-08-16 14:39:26
...被神仙吊打了...溜了
by DOCTYPE_OIers @ 2020-08-16 14:42:26
此题正解是递推
by Andy_chen @ 2020-08-16 14:59:02
难道是
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll C(int m,int n)
{
if(n<0 || m<0 || n<m)
return 0;
ll tot=1;
for(int i=1;i<=m;i++)
{
tot*=n-i+1;
tot/=i;
}
return tot;
}
int n,m,x,y;
int rt[5][5]={
0,0,1,0,0,
0,0,1,1,0,
0,0,0,1,1};
int dw[5][5]={
{},
{},
1,1,0,0,0,
0,1,1,0,0,
0,0,1,0,0};
int main()
{
cin>>n>>m>>x>>y;
if(n-x<3 && m-y<3)
{
x=n-x;
y=m-y;
}
if(x<3 && y<3)
{
int nx=2-x;
int ny=2-y;
ll tot=0;
tot+=C(n-x,m+n-x-y-3)*rt[nx][ny];
tot+=C(n-x-3,m+n-x-y-3)*dw[nx][ny];
cout<<tot;
return 0;
}
ll tot=C(n,n+m);
for(int i=-2;i<=2;i++)
tot-=C(x-i,x+y)*C(n-x+i,n+m-x-y);
tot+=C(x-3,x+y-1)*C(n-x+2,n+m-x-y-1);
tot+=C(x+2,x+y-1)*C(n-x-3,n+m-x-y-1);
tot+=C(x,x+y-3)*C(n-x-3,n+m-x-y-3);
tot+=C(x-3,x+y-3)*C(n-x,n+m-x-y-3);
cout<<tot;
return 0;
}
```
by Andy_chen @ 2020-08-16 14:59:52
~~神yummy不要打我~~
by Andy_chen @ 2020-08-16 15:00:21
我可能低估了这题的难度
~~啊我疯啦~~
by 已注销UyX2rX8tqz4TY @ 2020-08-18 12:23:36
你们只要亲测一下第4个数据文件:20 20 4 0就会知道,这玩意用int根本做不了啊!!!!
by bykem @ 2020-08-24 20:11:06