QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#778098#2811. NoMChiFAN100 ✓24ms3740kbC++141.2kb2024-11-24 12:38:502024-11-24 12:38:50

Judging History

This is the latest submission verdict.

  • [2024-11-24 12:38:50]
  • Judged
  • Verdict: 100
  • Time: 24ms
  • Memory: 3740kb
  • [2024-11-24 12:38:50]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
const int maxn = 4e3+114;
int fac[maxn],inv[maxn];
int iv[maxn];
int qpow(int a,int b){
    if(b==0) return 1;
    if(b==1) return a;
    int res=qpow(a,b/2);
    res=res*res%mod;
    if(b%2==1) res=res*a%mod;
    return res;
}
int dp[maxn];//全局选取 j 对的方案
int C(int n,int m){
    if(n<m) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int n,m,ans;
signed main(){
    fac[0]=inv[0]=1;
    for(int i=1;i<maxn;i++) fac[i]=fac[i-1]*i%mod,inv[i]=qpow(fac[i],mod-2);
    cin>>n>>m;
    n*=2;
    ans=C(n,n/2)*fac[n/2]%mod;
    if(n<=m){
        cout<<ans*fac[n/2]%mod<<'\n';
        return 0;
    }
    dp[0]=1;
    int sum=0;
    for(int p=0;p<m;p++){
        int cnt=(n-p)/m+(p==0?0:1);
        for(int i=sum;i>=0;i--){
             for(int j=1;j*2<=cnt;j++) dp[i+j]=(dp[i+j]+dp[i]*C(cnt,j*2)%mod*C(j*2,j)%mod*fac[j]%mod)%mod;
        }
        sum+=(cnt/2);
    }
    for(int j=1;j<=sum;j++){
        if(n-2*j!=0) dp[j]=dp[j]*C(n-2*j,(n-2*j)/2)%mod*fac[(n-2*j)/2]%mod;
        ans=(ans+dp[j]*(j%2==0?1:(mod-1))%mod)%mod;
    }
    cout<<ans*fac[n/2]%mod<<'\n';
    return 0;
}

详细

Subtask #1:

score: 9
Accepted

Test #1:

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

input:

1 1

output:

0

result:

ok single line: '0'

Test #2:

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

input:

2 1

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 2

output:

16

result:

ok single line: '16'

Test #4:

score: 9
Accepted
time: 0ms
memory: 3644kb

input:

3 1

output:

0

result:

ok single line: '0'

Test #5:

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

input:

3 2

output:

288

result:

ok single line: '288'

Test #6:

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

input:

3 3

output:

384

result:

ok single line: '384'

Test #7:

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

input:

4 2

output:

9216

result:

ok single line: '9216'

Test #8:

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

input:

4 3

output:

13824

result:

ok single line: '13824'

Test #9:

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

input:

5 1

output:

0

result:

ok single line: '0'

Test #10:

score: 9
Accepted
time: 0ms
memory: 3644kb

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: 1ms
memory: 3524kb

input:

99 55

output:

117836331

result:

ok single line: '117836331'

Test #12:

score: 12
Accepted
time: 2ms
memory: 3584kb

input:

69 50

output:

427094826

result:

ok single line: '427094826'

Test #13:

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

input:

67 5

output:

733227544

result:

ok single line: '733227544'

Test #14:

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

input:

69 26

output:

730153757

result:

ok single line: '730153757'

Test #15:

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

input:

71 64

output:

100578188

result:

ok single line: '100578188'

Test #16:

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

input:

87 10

output:

410973724

result:

ok single line: '410973724'

Test #17:

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

input:

64 35

output:

623989218

result:

ok single line: '623989218'

Test #18:

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

input:

67 51

output:

312068739

result:

ok single line: '312068739'

Test #19:

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

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: 1ms
memory: 3664kb

input:

164 20

output:

152386555

result:

ok single line: '152386555'

Test #21:

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

input:

154 80

output:

741601266

result:

ok single line: '741601266'

Test #22:

score: 13
Accepted
time: 2ms
memory: 3704kb

input:

266 255

output:

245915928

result:

ok single line: '245915928'

Test #23:

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

input:

239 19

output:

511848592

result:

ok single line: '511848592'

Test #24:

score: 13
Accepted
time: 2ms
memory: 3640kb

input:

296 141

output:

462138216

result:

ok single line: '462138216'

Test #25:

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

input:

255 250

output:

727256255

result:

ok single line: '727256255'

Test #26:

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

input:

257 15

output:

253032679

result:

ok single line: '253032679'

Test #27:

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

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: 3ms
memory: 3644kb

input:

625 19

output:

787742499

result:

ok single line: '787742499'

Test #29:

score: 18
Accepted
time: 4ms
memory: 3640kb

input:

657 324

output:

660247748

result:

ok single line: '660247748'

Test #30:

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

input:

646 582

output:

830442831

result:

ok single line: '830442831'

Test #31:

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

input:

637 14

output:

468904506

result:

ok single line: '468904506'

Test #32:

score: 18
Accepted
time: 4ms
memory: 3720kb

input:

685 343

output:

516203560

result:

ok single line: '516203560'

Test #33:

score: 18
Accepted
time: 4ms
memory: 3572kb

input:

713 644

output:

225559251

result:

ok single line: '225559251'

Test #34:

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

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: 15ms
memory: 3724kb

input:

1624 18

output:

887332511

result:

ok single line: '887332511'

Test #36:

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

input:

1779 1687

output:

611283083

result:

ok single line: '611283083'

Test #37:

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

input:

1603 18

output:

846564825

result:

ok single line: '846564825'

Test #38:

score: 48
Accepted
time: 16ms
memory: 3720kb

input:

1651 818

output:

148850576

result:

ok single line: '148850576'

Test #39:

score: 48
Accepted
time: 14ms
memory: 3596kb

input:

1579 1501

output:

427262684

result:

ok single line: '427262684'

Test #40:

score: 48
Accepted
time: 24ms
memory: 3724kb

input:

2000 1999

output:

510859110

result:

ok single line: '510859110'