QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113878 | #6653. 阴阳阵法 | xiaoyaowudi | AC ✓ | 195ms | 600940kb | C++17 | 1.3kb | 2023-06-19 22:04:03 | 2023-06-19 22:04:04 |
Judging History
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"