QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21409 | #2816. 过河卒二 | qingyu_orz# | RE | 0ms | 0kb | C++20 | 1.8kb | 2022-03-04 20:40:18 | 2022-05-08 03:12:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int p=59393;
int qow(int a,int n){
int ans=1;
for(;n;n>>=1){
if(n&1) ans=((long long)ans*a)%p;
a=((long long)a*a)%p;
}
return ans;
}
int fac[p+10000];
int infac[p+100000];
void init(){
fac[0]=1;
for(int i=1;i<p+50000;i++) fac[i]=((long long)fac[i-1]*i)%p;
for(int i=0;i<p+50000;i++) infac[i]=qow(fac[i],p-2);
}
inline int CCF(int n,int m){
if(n<0||m<0||n<m)return 0;
return ((((long long)infac[m]*infac[n-m])%p)*fac[n])%p;
}
inline int C(int n,int m){
if(n<p&&m<p)return CCF(n,m);
return 1ll*C(n/p,m/p)*CCF(n%p,m%p)%p;
}
int f(int s,int t){
int ans=0;
if(s<t) swap(s,t);
for(int a=0;a<=s;a++){
ans=(ans+(long long)C(s,a)*C(s+t-a,s))%p;
}
return ans;
}
int g(int s,int t){
if(s<t) swap(s,t);
int ans=0;
for(int a=0;a<=s;a++) ans=(ans+(long long)C(s,a)*C(s+t-a+1,s+1))%p;
for(int a=s,b=1;a>=0;a--,b=(b+C(t+s-a,t))%p) ans=(ans+(long long)C(t,a)*b)%p;
return (2*ans+p-f(s,t))%p;
}
int x[25],y[25];
pair<int,int>sh[25];
int F[25],G[25];
int main(){
init();
int n,m,k;
cin>>n>>m>>k;
--n,--m;
for(int i=1;i<=k;++i)cin>>x[i]>>y[i];
for(int i=1;i<=k;++i)--x[i],--y[i];
int GG=g(n,m);
for(int i=1;i<=k;++i){
F[i]=f(x[i],y[i]);
G[i]=g(n-x[i],m-y[i]);
}
int ans=0;
for(int i=0;i<(1<<k);++i){
int gs=1,tot=0;
for(int j=1;j<=k;++j){
if(i&(1<<(j-1)))gs=-gs;
sh[++tot]=make_pair(x[j],y[j]);
}
sort(sh+1,sh+tot+1);
for(int j=1;j<tot;++j){
if(sh[j].second>sh[j+1].second){
gs=0;
break;
}
}
int aa=0;
if(i==0)aa=GG;
else{
int A=0,B=0;
for(int j=1;j<=n;++j){
if(x[j]==sh[1].first&&y[j]==sh[1].second){
A=j;
}
if(x[j]==sh[tot].first&&y[j]==sh[tot].second){
B=j;
}
}
aa=1ll*F[A]*G[B]%p;
}
ans=(ans+1ll*gs*aa)%p;
}
cout<<(ans%p+p)%p<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
1737 2613 20 1695 2081 1449 1419 868 1636 879 2454 1400 1778 1364 2166 1343 1563 1229 2012 1308 1674 1712 2004 1392 1716 1118 1690 1693 1986 1641 2221 1454 1937 1554 1944 997 2083 1242 1503 990 1834 986 1438