QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#420370#2816. 过河卒二liqingyang#WA 68ms4132kbC++171.4kb2024-05-24 16:51:032024-05-24 16:51:09

Judging History

你现在查看的是最新测评结果

  • [2024-05-24 16:51:09]
  • 评测
  • 测评结果:WA
  • 用时:68ms
  • 内存:4132kb
  • [2024-05-24 16:51:03]
  • 提交

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'