传送门

啊啊啊啊啊没有组合数学的题单我怎么一直切水题啊$QAQ$

先设$f(n,m,k)$为在$n\times m$的矩形中放$k$个车的方案。

把这个阶梯状的棋盘分割成两个$a\times b$和$(a+c)\times d$的矩形。

然后枚举在这两个矩形放几个车。

答案就是$\sum\limits_{i=0}^kf(a,b,i)f(a+c-i,d,k-i)$

再来处理$f$。

显然在一个$n\times n$的棋盘里放$n$个车的方案数为$n!$。

从$n\times m$的棋盘里抽出一个$k\times k$的棋盘，有$C_n^kC_m^k$中方案。

那么$f(n,m,k)=C_n^kC_m^kk!$，注意特判$k>n,m$的情况。

这题就没了。

（数据范围明明可以开到$1e7$或者套个卢卡斯啊）

之所以挂上枚举的标签是因为我觉得这就是枚举（雾

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 3005
#define inf 0x3f3f3f3f

const int mod = 100003;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int fac[maxn]={1},inv[maxn];
int INV(int x){return x==1?1:1ll*(mod-mod/x)*INV(mod%x)%mod;}
inline int C(int n,int m){
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
inline int f(int n,int m,int k){
    if(k>n||k>m)return 0;
    return 1ll*C(n,k)*C(m,k)%mod*fac[k]%mod;
}
int main(){
    int a=read(),b=read(),c=read(),d=read(),k=read(),tp=max(b,max(a+c,d)),ans=0;
    for(register int i=1;i<=tp;++i)fac[i]=1ll*fac[i-1]*i%mod;
    inv[tp]=INV(fac[tp]);
    for(register int i=tp-1;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    for(register int i=0;i<=k;++i)(ans+=1ll*f(a,b,i)*f(a+c-i,d,k-i)%mod)%=mod;
    printf("%d\n",ans);
}