QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#425652#2811. NoMship2077100 ✓17ms4020kbC++141.2kb2024-05-30 15:20:362024-05-30 15:20:36

Judging History

This is the latest submission verdict.

  • [2024-05-30 15:20:36]
  • Judged
  • Verdict: 100
  • Time: 17ms
  • Memory: 4020kb
  • [2024-05-30 15:20:36]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int M=2005,mod=1e9+7;
int n,m,N;long long ans;
int f[M],g[M],pw[M],fac[M],ifac[M],coef[M];
int qpow(int x,int n){
    int s=1; while (n){
        if (n&1) s=1ll*s*x%mod;
        x=1ll*x*x%mod; n>>=1;
    } return s;
}
int rdc(int x){return x>=mod?x-mod:x;}
void init(){
    for (int i=pw[0]=1;i<=n;i++) pw[i]=rdc(pw[i-1]<<1);
    for (int i=fac[0]=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (int i=n;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
    for (int i=coef[0]=1;i<=n;i++) coef[i]=1ll*coef[i-1]*(i*2-1)%mod;
}
int c(int n,int m){return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
int main(){
    scanf("%d%d",&n,&m);
    init();f[0]=1;N=n<<1;
    for (int i=0,sum=0;i<m;i++){
        int len=i<N%m?N/m+1:N/m;
        for (int j=0;j<=sum;j++) g[j]=f[j],f[j]=0;
        for (int j=0;j<=sum;j++)
            for (int k=0;k*2<=len;k++)
                f[j+k]=(f[j+k]+1ll*g[j]*coef[k]%mod*c(len,k<<1))%mod;
        sum+=len>>1;
    }
    for (int i=0;i<=n;i++){
        int rec=1ll*f[i]*coef[n-i]%mod;
        ans+=i&1?-rec:rec;
    }
    ans%=mod;if (ans<0) ans+=mod;
    printf("%d\n",1ll*ans*fac[n]%mod*pw[n]%mod);
    return 0;
}

詳細信息

Subtask #1:

score: 9
Accepted

Test #1:

score: 9
Accepted
time: 1ms
memory: 3952kb

input:

1 1

output:

0

result:

ok single line: '0'

Test #2:

score: 9
Accepted
time: 1ms
memory: 3816kb

input:

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: 9
Accepted
time: 1ms
memory: 3812kb

input:

2 2

output:

16

result:

ok single line: '16'

Test #4:

score: 9
Accepted
time: 1ms
memory: 3808kb

input:

3 1

output:

0

result:

ok single line: '0'

Test #5:

score: 9
Accepted
time: 1ms
memory: 3952kb

input:

3 2

output:

288

result:

ok single line: '288'

Test #6:

score: 9
Accepted
time: 1ms
memory: 3996kb

input:

3 3

output:

384

result:

ok single line: '384'

Test #7:

score: 9
Accepted
time: 1ms
memory: 3808kb

input:

4 2

output:

9216

result:

ok single line: '9216'

Test #8:

score: 9
Accepted
time: 1ms
memory: 3996kb

input:

4 3

output:

13824

result:

ok single line: '13824'

Test #9:

score: 9
Accepted
time: 1ms
memory: 3996kb

input:

5 1

output:

0

result:

ok single line: '0'

Test #10:

score: 9
Accepted
time: 1ms
memory: 3952kb

input:

5 5

output:

2088960

result:

ok single line: '2088960'

Subtask #2:

score: 12
Accepted

Dependency #1:

100%
Accepted

Test #11:

score: 12
Accepted
time: 0ms
memory: 3972kb

input:

99 55

output:

117836331

result:

ok single line: '117836331'

Test #12:

score: 12
Accepted
time: 1ms
memory: 3964kb

input:

69 50

output:

427094826

result:

ok single line: '427094826'

Test #13:

score: 12
Accepted
time: 1ms
memory: 3960kb

input:

67 5

output:

733227544

result:

ok single line: '733227544'

Test #14:

score: 12
Accepted
time: 1ms
memory: 3868kb

input:

69 26

output:

730153757

result:

ok single line: '730153757'

Test #15:

score: 12
Accepted
time: 1ms
memory: 3960kb

input:

71 64

output:

100578188

result:

ok single line: '100578188'

Test #16:

score: 12
Accepted
time: 1ms
memory: 3936kb

input:

87 10

output:

410973724

result:

ok single line: '410973724'

Test #17:

score: 12
Accepted
time: 1ms
memory: 3820kb

input:

64 35

output:

623989218

result:

ok single line: '623989218'

Test #18:

score: 12
Accepted
time: 1ms
memory: 3948kb

input:

67 51

output:

312068739

result:

ok single line: '312068739'

Test #19:

score: 12
Accepted
time: 1ms
memory: 3960kb

input:

85 3

output:

796582412

result:

ok single line: '796582412'

Subtask #3:

score: 13
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #20:

score: 13
Accepted
time: 0ms
memory: 3968kb

input:

164 20

output:

152386555

result:

ok single line: '152386555'

Test #21:

score: 13
Accepted
time: 1ms
memory: 3956kb

input:

154 80

output:

741601266

result:

ok single line: '741601266'

Test #22:

score: 13
Accepted
time: 1ms
memory: 3888kb

input:

266 255

output:

245915928

result:

ok single line: '245915928'

Test #23:

score: 13
Accepted
time: 0ms
memory: 3956kb

input:

239 19

output:

511848592

result:

ok single line: '511848592'

Test #24:

score: 13
Accepted
time: 1ms
memory: 3976kb

input:

296 141

output:

462138216

result:

ok single line: '462138216'

Test #25:

score: 13
Accepted
time: 1ms
memory: 4016kb

input:

255 250

output:

727256255

result:

ok single line: '727256255'

Test #26:

score: 13
Accepted
time: 1ms
memory: 3884kb

input:

257 15

output:

253032679

result:

ok single line: '253032679'

Test #27:

score: 13
Accepted
time: 1ms
memory: 3972kb

input:

300 299

output:

559277735

result:

ok single line: '559277735'

Subtask #4:

score: 18
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #28:

score: 18
Accepted
time: 2ms
memory: 3832kb

input:

625 19

output:

787742499

result:

ok single line: '787742499'

Test #29:

score: 18
Accepted
time: 2ms
memory: 3872kb

input:

657 324

output:

660247748

result:

ok single line: '660247748'

Test #30:

score: 18
Accepted
time: 2ms
memory: 3872kb

input:

646 582

output:

830442831

result:

ok single line: '830442831'

Test #31:

score: 18
Accepted
time: 2ms
memory: 3976kb

input:

637 14

output:

468904506

result:

ok single line: '468904506'

Test #32:

score: 18
Accepted
time: 2ms
memory: 3912kb

input:

685 343

output:

516203560

result:

ok single line: '516203560'

Test #33:

score: 18
Accepted
time: 3ms
memory: 3888kb

input:

713 644

output:

225559251

result:

ok single line: '225559251'

Test #34:

score: 18
Accepted
time: 5ms
memory: 4020kb

input:

900 899

output:

941929065

result:

ok single line: '941929065'

Subtask #5:

score: 48
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #35:

score: 48
Accepted
time: 3ms
memory: 3880kb

input:

1624 18

output:

887332511

result:

ok single line: '887332511'

Test #36:

score: 48
Accepted
time: 15ms
memory: 3952kb

input:

1779 1687

output:

611283083

result:

ok single line: '611283083'

Test #37:

score: 48
Accepted
time: 6ms
memory: 3972kb

input:

1603 18

output:

846564825

result:

ok single line: '846564825'

Test #38:

score: 48
Accepted
time: 7ms
memory: 3952kb

input:

1651 818

output:

148850576

result:

ok single line: '148850576'

Test #39:

score: 48
Accepted
time: 12ms
memory: 3916kb

input:

1579 1501

output:

427262684

result:

ok single line: '427262684'

Test #40:

score: 48
Accepted
time: 17ms
memory: 3956kb

input:

2000 1999

output:

510859110

result:

ok single line: '510859110'