HEX SDUT 3896 17年山东省赛D题
这个题是从矩形的左下角走到右上角的方案数的变形题，看来我对以前做过的题理解还不是太深，或者是忘了。对于这种题目，直接分析它的性质就完事了。从（1，1）走到（a,b）向左走的步数和向右走的步数是确定的，向下是代表向左向右各走了一步。细节：利用对称性，线性推逆元
对于每一种情况，向左下、向右下、向下的次数都是确定的，然后，对于每一种方向内部顺序不用考虑，然后排列组合就完事了
对称性上又出错了，哎，自己也没找个小数据试一下，就...(a,b)和(a,a-b+1)是对称的
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<cstring>
#define inf 2147483647
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,nl,mid,l,r
#define rson rs,mid+1,nr,l,r
#define N 100010
#define For(i,a,b) for(long long i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar() using namespace std;
long long l,r,x,y,d;
long long a[],inv[];
long long p=;
long long ans;
long long down; void in(long long &x){
long long y=;
char c=g();x=;
while(c<''||c>''){
if(c=='-')y=-;
c=g();
}
while(c<=''&&c>=''){
x=(x<<)+(x<<)+c-'';c=g();
}
x*=y;
}
void o(long long x){
if(x<){
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
} long long ksm(long long a,long long b,long long p){
while(b%==){
a*=a;
a%=p;
b>>=;
}
long long r=;
while(b>){
if(b%==){
r*=a;
r%=p;
}
a*=a;
a%=p;
b>>=;
}
return r;
} void clear(){
ans=;
down=;
} int main(){
a[]=;
For(i,,)
a[i]=(a[i-]*i)%p;
For(i,,)
inv[i]=ksm(a[i],p-,p)%p;
while(cin>>x>>y){
clear();
y=max(y,x-y+);
l=x-y;
r=y-;
while(l>=&&r>=){
ans+=a[l+r+down]*inv[l]%p*inv[r]%p*inv[down]%p;
ans%=p;
l--;
r--;
down++;
}
o(ans);p('\n');
}
return ;
}