QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#502836	#2573. Two Permutations	yingxilin	AC ✓	77ms	12284kb	C++14	895b	2024-08-03 15:06:08	2024-08-03 15:06:09

Judging History

你现在查看的是最新测评结果

[2024-08-03 15:06:09]
评测

测评结果：AC
用时：77ms
内存：12284kb

查看

[2024-08-03 15:06:08]
提交

answer

#include <bits/stdc++.h>
using namespace std;
const int  mod = (1e9+7);
int n,k,now=0,last=0,dp[2][110][10010];
int main()
{

    cin>>n>>k;
    dp[0][0][0]=1;

    for(int i=1;i<=n;i++)
    {
        now=1-now,last=1-now;
        memset(dp[now],0,sizeof dp[now]);
        int val=i;
        for(int j=0;j<=min(n,i);j++) for(int p=0;p<=k;p++){
            if(!dp[last][j][p]) continue;

            dp[now][j][p]=(dp[now][j][p]+dp[last][j][p])%mod;

            int res=i*2-j*2-2;

            if(res>1 && val*2+p<=k) 
              dp[now][j+2][p+val*2]=(dp[now][j+2][p+val*2]+1ll*dp[last][j][p]*res/2%mod*res/2)%mod;
            if(res>=0 && val+p<=k) 
              dp[now][j+1][p+val]=(dp[now][j+1][p+val]+1ll*dp[last][j][p]*(1+res))%mod;
        }
    }

    int ans=dp[now][n][k];
    for(int i=2;i<=n;i++) ans=1ll*ans*i%mod;
    cout<<ans;
    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 12228kb

input:

2 4

output:

result:

ok 1 number(s): "2"

Test #2:

score: 0

Accepted

time: 2ms

memory: 12220kb

input:

3 7

output:

result:

ok 1 number(s): "12"

Test #3:

score: 0

Accepted

time: 2ms

memory: 12208kb

input:

4 10

output:

result:

ok 1 number(s): "24"

Test #4:

score: 0

Accepted

time: 2ms

memory: 12284kb

input:

4 14

output:

result:

ok 1 number(s): "96"

Test #5:

score: 0

Accepted

time: 2ms

memory: 12128kb

input:

5 10

output:

result:

ok 1 number(s): "0"

Test #6:

score: 0

Accepted

time: 0ms

memory: 12136kb

input:

5 15

output:

result:

ok 1 number(s): "120"

Test #7:

score: 0

Accepted

time: 3ms

memory: 12196kb

input:

5 21

output:

result:

ok 1 number(s): "2400"

Test #8:

score: 0

Accepted

time: 3ms

memory: 12156kb

input:

6 21

output:

result:

ok 1 number(s): "720"

Test #9:

score: 0

Accepted

time: 0ms

memory: 12280kb

input:

6 30

output:

result:

ok 1 number(s): "25920"

Test #10:

score: 0

Accepted

time: 3ms

memory: 12224kb

input:

6 27

output:

result:

ok 1 number(s): "106560"

Test #11:

score: 0

Accepted

time: 0ms

memory: 12188kb

input:

20 300

output:

644873710

result:

ok 1 number(s): "644873710"

Test #12:

score: 0

Accepted

time: 4ms

memory: 12276kb

input:

20 139

output:

result:

ok 1 number(s): "0"

Test #13:

score: 0

Accepted

time: 3ms

memory: 12140kb

input:

30 470

output:

491424690

result:

ok 1 number(s): "491424690"

Test #14:

score: 0

Accepted

time: 3ms

memory: 12204kb

input:

30 500

output:

result:

ok 1 number(s): "8436035"

Test #15:

score: 0

Accepted

time: 9ms

memory: 12280kb

input:

40 1000

output:

617159088

result:

ok 1 number(s): "617159088"

Test #16:

score: 0

Accepted

time: 9ms

memory: 12156kb

input:

40 900

output:

729805907

result:

ok 1 number(s): "729805907"

Test #17:

score: 0

Accepted

time: 13ms

memory: 12280kb

input:

60 1830

output:

16340084

result:

ok 1 number(s): "16340084"

Test #18:

score: 0

Accepted

time: 12ms

memory: 12212kb

input:

60 2000

output:

832198921

result:

ok 1 number(s): "832198921"

Test #19:

score: 0

Accepted

time: 60ms

memory: 12204kb

input:

100 5050

output:

437918130

result:

ok 1 number(s): "437918130"

Test #20:

score: 0

Accepted

time: 22ms

memory: 12208kb

input:

100 700

output:

result:

ok 1 number(s): "0"

Test #21:

score: 0

Accepted

time: 77ms

memory: 12160kb

input:

100 10000

output:

result:

ok 1 number(s): "0"