QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85769 | #977. Local Maxima | s8194272 | AC ✓ | 1576ms | 214820kb | C++14 | 1.9kb | 2023-03-08 14:37:09 | 2023-03-08 14:37:10 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<random>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define int long long
#define fi first
#define se second
#define max Max
#define min Min
#define abs Abs
#define lc (x<<1)
#define rc (x<<1|1)
#define mid ((l+r)>>1)
#define pb(x) push_back(x)
#define lowbit(x) ((x)&(-(x)))
#define fan(x) ((((x)-1)^1)+1)
#define mp(x,y) make_pair(x,y)
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
#define SZ(x) ((int)(x.size()))
#define INF 0x3f3f3f3f
using namespace std;
inline int read()
{
int ans=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=(ans<<1)+(ans<<3)+c-'0';c=getchar();}
return ans*f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x/10) write(x/10);
putchar((char)(x%10)+'0');
}
template<typename T>inline T Abs(T a){return a>0?a:-a;};
template<typename T,typename TT>inline T Min(T a,TT b){return a<b?a:b;}
template<typename T,typename TT> inline T Max(T a,TT b){return a<b?b:a;}
const int N=3005;
int n,m,p,f[N][N],jc[N*N],inv[N*N];
inline int q_pow(int a,int b)
{
int c=1;
while(b)
{
if(b&1) c=a*c%p;
a=a*a%p;b>>=1;
}
return c;
}
inline void init(int x)
{
jc[0]=1;
for(int i=1;i<=x;++i)
jc[i]=jc[i-1]*i%p;
inv[x]=q_pow(jc[x],p-2);
for(int i=x-1;i>=0;--i)
inv[i]=inv[i+1]*(i+1)%p;
}
inline int C(int n,int m)
{
return n<m?0:jc[n]*inv[m]%p*inv[n-m]%p;
}
signed main()
{
n=read();m=read();p=read();
init(n*m);f[1][1]=n*m%p;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
if(i!=n) f[i+1][j]=(f[i+1][j]+f[i][j]*(n-i)*j%p*jc[n*m-i*j-1]%p*inv[n*m-(i+1)*j])%p;
if(j!=m) f[i][j+1]=(f[i][j+1]+f[i][j]*(m-j)*i%p*jc[n*m-i*j-1]%p*inv[n*m-i*(j+1)])%p;
}
write(f[n][m]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7556kb
input:
2 2 1000000007
output:
16
result:
ok "16"
Test #2:
score: 0
Accepted
time: 3ms
memory: 7404kb
input:
4 3 1000000007
output:
95800320
result:
ok "95800320"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7948kb
input:
100 100 998244353
output:
848530760
result:
ok "848530760"
Test #4:
score: 0
Accepted
time: 2ms
memory: 7456kb
input:
79 78 435515903
output:
306910591
result:
ok "306910591"
Test #5:
score: 0
Accepted
time: 1ms
memory: 7704kb
input:
69 74 715090997
output:
611101520
result:
ok "611101520"
Test #6:
score: 0
Accepted
time: 4ms
memory: 7784kb
input:
77 67 221878187
output:
215381310
result:
ok "215381310"
Test #7:
score: 0
Accepted
time: 5ms
memory: 7688kb
input:
70 66 537039721
output:
352526401
result:
ok "352526401"
Test #8:
score: 0
Accepted
time: 1311ms
memory: 185132kb
input:
2952 2408 973899449
output:
400429421
result:
ok "400429421"
Test #9:
score: 0
Accepted
time: 1100ms
memory: 158716kb
input:
2484 2435 713449813
output:
79762013
result:
ok "79762013"
Test #10:
score: 0
Accepted
time: 1460ms
memory: 200300kb
input:
2904 2783 227396761
output:
120446329
result:
ok "120446329"
Test #11:
score: 0
Accepted
time: 1366ms
memory: 190348kb
input:
2654 2908 161249083
output:
100452853
result:
ok "100452853"
Test #12:
score: 0
Accepted
time: 1379ms
memory: 190128kb
input:
2819 2657 722796007
output:
643358934
result:
ok "643358934"
Test #13:
score: 0
Accepted
time: 1576ms
memory: 214820kb
input:
3000 3000 143115311
output:
76718331
result:
ok "76718331"