QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#420370 | #2816. 过河卒二 | liqingyang# | WA | 68ms | 4132kb | C++17 | 1.4kb | 2024-05-24 16:51:03 | 2024-05-24 16:51:09 |
Judging History
answer
#include<iostream>
#include<algorithm>
using namespace std;
const int mod=59393;
inline int qpow(int a,int b)
{
int ret=1;
while(b)
{
if(b&1)
{
ret=(long long)
ret*a%mod;
}
a=(long long)
a*a%mod,b>>=1;
}
return ret;
}
int n,m,K,s[mod+5],inv[mod+5],f[25][25];
pair<int,int> a[25];
inline int C(int n,int m)
{
return n<m?0:(n<mod?(long long)s[n]*inv[m]*inv[n-m]%mod
:(long long)C(n/mod,m/mod)*C(n%mod,m%mod)%mod);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
for(int i=s[0]=inv[0]=1;i<=mod;i++)
{
s[i]=(long long)s[i-1]*i%mod;
inv[i]=qpow(s[i],mod-2);
}
cin>>n>>m>>K;
for(int i=1;i<=K;i++)
{
cin>>a[i].first>>a[i].second;
}
sort(a+1,a+K+1);
a[0]={1,1},a[++K]={n+1,m+1};
for(int i=0;i<=K;i++)
{
for(int j=i+1;j<=K;j++)
{
if(a[i].second>a[j].second)
{
continue;
}
int n=a[j].first-a[i].first;
int m=a[j].second-a[i].second;
long long sum=0;
for(int k=0;k<=min(n,m);k++)
{
sum+=(long long)
C(n-k+m-k+k,k)*C(n-k+m-k,n-k);
}
f[i][j]=sum%mod;
}
}
long long Ans=0;
for(int i=0;i<(1<<K-1);i++)
{
int last=0,ans=1;
for(int j=1;j<K;j++)
{
if(i&(1<<j-1))
{
ans=(long long)
ans*f[last][j];
last=j;
}
}
ans=(long long)ans*f[last][K];
Ans+=((__builtin_popcount(i)&1)?-1:1)*ans;
}
cout<<(Ans%mod+mod)%mod<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 68ms
memory: 4132kb
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
output:
22051
result:
wrong answer 1st lines differ - expected: '47388', found: '22051'