QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113878#6653. 阴阳阵法xiaoyaowudiAC ✓195ms600940kbC++171.3kb2023-06-19 22:04:032023-06-19 22:04:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-19 22:04:04]
  • 评测
  • 测评结果:AC
  • 用时:195ms
  • 内存:600940kb
  • [2023-06-19 22:04:03]
  • 提交

answer

#include <algorithm>
#include <iostream>
constexpr int N(2e3+10);
using ull=unsigned long long;
using L=__uint128_t;
struct FM
{
	ull b,m;
	FM(ull p):b(p),m((L(1)<<64)/p){}
	ull R(ull t)
	{
		ull a((L(t)*m)>>64);
		ull c=t-a*b;
		return c>=b?c-b:c;
	}
}F(2);
ull f[N][N],h[N][N][2],g[N][N][2][2][2][2];
int main()
{
	std::ios::sync_with_stdio(false);int n,m,p;
	std::cin.tie(nullptr);std::cin>>n>>m>>p;F=FM(p);
	f[0][0]=1;
	for(int i(0);i<=n;++i) for(int j(0);j<=m;++j)
	{
		f[i][j]=F.R(f[i][j]);for(int k(0);k<2;++k){h[i][j][k]=F.R(h[i][j][k]);}
		ull v1(1ull*f[i][j]*(n-i-1)),v2(1ull*f[i][j]*(m-j));
		f[i+1][j]+=1ull*f[i][j]*(i+j+1)+h[i][j][0]+h[i][j][1];
		h[i+1][j][0]+=v1*(i+j+1)+1ull*(h[i][j][0]+h[i][j][1])*(n-i-1);
		h[i][j+1][1]+=v2*i+1ull*h[i][j][0]*(m-j);
		g[i+1][j][0][0][1][0]+=v1;
		g[i][j+1][1][1][0][1]+=v2;
		for(int k(0);k<2;++k) for(int t(0);t<2;++t) for(int l(0);l<2;++l) for(int r(0);r<2;++r)
		{
			ull a(F.R(g[i][j][k][t][l][r])),b(1ull*a*(n-i-1)),c(1ull*a*(m-j));
			if(!((l^1)&r)) f[i+1][j]+=a,h[i+1][j][0]+=b;
			if(!k && !t && !(l&(r^1))) h[i][j+1][1]+=c;
			g[i+1][j][k][0][l^1][r]+=b;
			if(!t) g[i][j+1][k][1][l][r^1]+=c;
		}
	}
	int ans(0);
	for(int i(m),t(1);i>=0;--i,t=F.R(1ull*t*n)) ans=F.R(ans+1ull*f[n][i]*t);
	std::cout<<ans<<std::endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 153ms
memory: 599000kb

input:

2000 1969 999999999

output:

770055336

result:

ok 1 number(s): "770055336"

Test #2:

score: 0
Accepted
time: 3ms
memory: 28292kb

input:

1888 1 8000000

output:

1719872

result:

ok 1 number(s): "1719872"

Test #3:

score: 0
Accepted
time: 2ms
memory: 6336kb

input:

1 2000 79993339

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 195ms
memory: 600840kb

input:

1999 1999 2000

output:

1696

result:

ok 1 number(s): "1696"

Test #5:

score: 0
Accepted
time: 107ms
memory: 432732kb

input:

1518 1838 998244853

output:

835766872

result:

ok 1 number(s): "835766872"

Test #6:

score: 0
Accepted
time: 4ms
memory: 9860kb

input:

16 1666 17795

output:

15253

result:

ok 1 number(s): "15253"

Test #7:

score: 0
Accepted
time: 131ms
memory: 600940kb

input:

2000 2000 1

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 1ms
memory: 5932kb

input:

19 69 4

output:

0

result:

ok 1 number(s): "0"

Test #9:

score: 0
Accepted
time: 2ms
memory: 6824kb

input:

62 62 63

output:

7

result:

ok 1 number(s): "7"

Test #10:

score: 0
Accepted
time: 152ms
memory: 544024kb

input:

1809 1998 536870912

output:

159234561

result:

ok 1 number(s): "159234561"