QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#839819 | #8728. Tablica | kkkgjyismine4 | 100 ✓ | 139ms | 141152kb | C++20 | 1.0kb | 2025-01-02 10:14:54 | 2025-01-02 10:14:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,inv2=(mod+1>>1);
void add(int &x,const int y){
if((x+=y)>=mod)x-=mod;
}
int mul(int x,int y){
return 1ll*x*y%mod;
}
int n,m;
#define N 3005
int f[N],g[N][N],C[N*2][N*2],ipw[N*2],fac[N*2];
int slv(int p,int q){
int s=0,ct=m+q;
for(int i=0;i<=min(p,q);++i){
int s1=mul(mul(C[p][i],C[q][i]),fac[i]);
int ct1=ct-2*i;
s1=mul(s1,mul(C[ct1][n-p],fac[n-p]));
if((ct1-n+p)&1)continue;
s1=mul(s1,f[ct1-n+p>>1]);
if(i&1)add(s,mod-s1);
else add(s,s1);
}
return mul(s,ipw[q]);
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m,ipw[0]=fac[0]=1;
for(int i=1;i<=(N-5<<1);++i)fac[i]=mul(i,fac[i-1]);
for(int i=0;i<=(N-5<<1);++i){
C[i][0]=1;if(i)ipw[i]=mul(inv2,ipw[i-1]);
for(int j=1;j<=i;++j)C[i][j]=C[i-1][j-1],add(C[i][j],C[i-1][j]);
}
f[0]=1;int ans=0;
for(int i=1;i<=m;++i)f[i]=mul(f[i-1],C[i*2][2]);
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j)
if(n+i==m+j)add(ans,mul(C[n][i],mul(C[m][j],slv(i,j))));
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 56ms
memory: 133864kb
input:
5 6
output:
456750
result:
ok 1 number(s): "456750"
Test #2:
score: 10
Accepted
time: 55ms
memory: 138640kb
input:
6 6
output:
5464710
result:
ok 1 number(s): "5464710"
Test #3:
score: 10
Accepted
time: 61ms
memory: 139500kb
input:
3 5
output:
270
result:
ok 1 number(s): "270"
Test #4:
score: 10
Accepted
time: 68ms
memory: 140568kb
input:
3 6
output:
90
result:
ok 1 number(s): "90"
Test #5:
score: 10
Accepted
time: 52ms
memory: 139508kb
input:
4 6
output:
14580
result:
ok 1 number(s): "14580"
Test #6:
score: 10
Accepted
time: 58ms
memory: 140292kb
input:
3 4
output:
270
result:
ok 1 number(s): "270"
Subtask #2:
score: 18
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 18
Accepted
time: 72ms
memory: 139912kb
input:
50 49
output:
750700714
result:
ok 1 number(s): "750700714"
Test #8:
score: 18
Accepted
time: 60ms
memory: 140284kb
input:
50 50
output:
630532893
result:
ok 1 number(s): "630532893"
Test #9:
score: 18
Accepted
time: 60ms
memory: 140440kb
input:
41 34
output:
800856205
result:
ok 1 number(s): "800856205"
Test #10:
score: 18
Accepted
time: 46ms
memory: 139748kb
input:
39 41
output:
541550932
result:
ok 1 number(s): "541550932"
Test #11:
score: 18
Accepted
time: 58ms
memory: 140580kb
input:
38 46
output:
651393374
result:
ok 1 number(s): "651393374"
Test #12:
score: 18
Accepted
time: 61ms
memory: 140240kb
input:
37 39
output:
746919932
result:
ok 1 number(s): "746919932"
Test #13:
score: 18
Accepted
time: 46ms
memory: 140692kb
input:
30 50
output:
214086425
result:
ok 1 number(s): "214086425"
Test #14:
score: 18
Accepted
time: 56ms
memory: 140564kb
input:
50 41
output:
193351204
result:
ok 1 number(s): "193351204"
Test #15:
score: 18
Accepted
time: 56ms
memory: 140724kb
input:
44 32
output:
63855946
result:
ok 1 number(s): "63855946"
Test #16:
score: 18
Accepted
time: 69ms
memory: 140844kb
input:
45 42
output:
266239299
result:
ok 1 number(s): "266239299"
Subtask #3:
score: 31
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #17:
score: 31
Accepted
time: 69ms
memory: 140676kb
input:
199 200
output:
841552647
result:
ok 1 number(s): "841552647"
Test #18:
score: 31
Accepted
time: 48ms
memory: 140608kb
input:
200 200
output:
157842226
result:
ok 1 number(s): "157842226"
Test #19:
score: 31
Accepted
time: 62ms
memory: 140012kb
input:
156 199
output:
216453917
result:
ok 1 number(s): "216453917"
Test #20:
score: 31
Accepted
time: 61ms
memory: 140040kb
input:
161 199
output:
539960909
result:
ok 1 number(s): "539960909"
Test #21:
score: 31
Accepted
time: 50ms
memory: 140708kb
input:
194 160
output:
764024671
result:
ok 1 number(s): "764024671"
Test #22:
score: 31
Accepted
time: 62ms
memory: 140200kb
input:
184 195
output:
117763744
result:
ok 1 number(s): "117763744"
Test #23:
score: 31
Accepted
time: 66ms
memory: 140668kb
input:
152 174
output:
350941677
result:
ok 1 number(s): "350941677"
Test #24:
score: 31
Accepted
time: 61ms
memory: 139564kb
input:
195 186
output:
130526660
result:
ok 1 number(s): "130526660"
Test #25:
score: 31
Accepted
time: 60ms
memory: 139860kb
input:
173 159
output:
754934766
result:
ok 1 number(s): "754934766"
Test #26:
score: 31
Accepted
time: 66ms
memory: 139624kb
input:
194 170
output:
956364877
result:
ok 1 number(s): "956364877"
Subtask #4:
score: 41
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #27:
score: 41
Accepted
time: 136ms
memory: 140252kb
input:
3000 2999
output:
5195706
result:
ok 1 number(s): "5195706"
Test #28:
score: 41
Accepted
time: 139ms
memory: 140152kb
input:
3000 3000
output:
224347336
result:
ok 1 number(s): "224347336"
Test #29:
score: 41
Accepted
time: 122ms
memory: 141088kb
input:
2854 2864
output:
513408195
result:
ok 1 number(s): "513408195"
Test #30:
score: 41
Accepted
time: 135ms
memory: 140344kb
input:
2887 2803
output:
58832696
result:
ok 1 number(s): "58832696"
Test #31:
score: 41
Accepted
time: 132ms
memory: 141056kb
input:
2800 2925
output:
804387597
result:
ok 1 number(s): "804387597"
Test #32:
score: 41
Accepted
time: 121ms
memory: 140232kb
input:
2842 2813
output:
971828715
result:
ok 1 number(s): "971828715"
Test #33:
score: 41
Accepted
time: 125ms
memory: 140364kb
input:
2808 2972
output:
329457042
result:
ok 1 number(s): "329457042"
Test #34:
score: 41
Accepted
time: 132ms
memory: 140008kb
input:
2821 2853
output:
81282690
result:
ok 1 number(s): "81282690"
Test #35:
score: 41
Accepted
time: 118ms
memory: 141152kb
input:
2875 2956
output:
105351485
result:
ok 1 number(s): "105351485"
Test #36:
score: 41
Accepted
time: 127ms
memory: 140396kb
input:
2879 2852
output:
672034506
result:
ok 1 number(s): "672034506"
Extra Test:
score: 0
Extra Test Passed