QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#346317	#7759. Permutation Counting 2	yingxue_cat	50	103ms	29016kb	C++14	1.4kb	2024-03-08 10:50:00	2024-03-08 10:50:01

Judging History

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

[2024-03-08 10:50:01]
评测

测评结果：50
用时：103ms
内存：29016kb

查看

[2024-03-08 10:50:00]
提交

answer

#include<bits/stdc++.h>
#define il inline
using namespace std;
il long long read()
{
    int xr=0,F=1; char cr;
    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
    while(cr>='0'&&cr<='9') 
        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
    return xr*F;
}
const int N=41;
int n,mod;
int f[N][N][N][N][N];
il void add(int &x,int y) {x+=y;if(x>=mod) x-=mod;}
int main()
{
    n=read(),mod=read();
    f[1][1][1][0][0]=1;
    for(int i=1;i<n;i++)
    for(int j=1;j<=min(i,n-i+1);j++)
        for(int id=1;id<=j;id++)
            for(int x=0;x<i;x++)
                for(int y=0;y<i;y++)
                {
                    for(int nxt=1;nxt<=j+1;nxt++)
                    {
                        // cout<<i<<" "<<j<<" "<<nxt<<" "<<x<<" "<<y<<" "<<f[i][j][id][x][y]<<endl;
                        if(nxt!=1&&nxt!=j+1&&j>=2) //merge 
                        {
                            add(f[i+1][j-1][nxt-1][x+1][y+(nxt>id)],f[i][j][id][x][y]);
                        }
                        add(f[i+1][j+1][nxt][x][y+(nxt>id)],f[i][j][id][x][y]);
                        if(nxt!=j+1) add(f[i+1][j][nxt][x][y+(nxt>id)],f[i][j][id][x][y]);
                        if(nxt!=1) add(f[i+1][j][nxt-1][x+1][y+(nxt>id)],f[i][j][id][x][y]);
                    }
                }
    for(int x=0;x<n;x++,printf("\n"))
        for(int y=0;y<n;y++)
            printf("%d ",f[n][1][1][x][y]);
    return 0;
}
/*
3 1000000007
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10

Accepted

Test #1:

score: 10

Accepted

time: 1ms

memory: 6140kb

input:

7 1001458121

output:

1 0 0 0 0 0 0 
0 56 56 8 0 0 0 
0 56 659 440 36 0 0 
0 8 440 1520 440 8 0 
0 0 36 440 659 56 0 
0 0 0 8 56 56 0 
0 0 0 0 0 0 1

result:

ok 49 tokens

Test #2:

score: 0

Accepted

time: 1ms

memory: 6112kb

input:

8 1008735209

output:

1 0 0 0 0 0 0 0 
0 84 126 36 1 0 0 0 
0 126 1773 1980 405 9 0 0 
0 36 1980 8436 4761 405 1 0 
0 1 405 4761 8436 1980 36 0 
0 0 9 405 1980 1773 126 0 
0 0 0 1 36 126 84 0 
0 0 0 0 0 0 0 1

result:

ok 64 tokens

Subtask #2:

score: 15

Accepted

Test #3:

score: 15

Accepted

time: 2ms

memory: 7044kb

input:

14 1000253273

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 455 3003 6435 5005 1365 105 1 0 0 0 0 0 0 
0 3003 112905 730665 1629435 1456560 529956 71940 2835 15 0 0 0 0 
0 6435 730665 10865585 46433475 75169560 50184540 13633740 1349931 36735 120 0 0 0 
0 5005 1629435 46433475 336576825 860578230 885230850 375891370 62035485 33...

result:

ok 196 tokens

Test #4:

score: 0

Accepted

time: 0ms

memory: 7284kb

input:

15 1009800301

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 560 4368 11440 11440 4368 560 16 0 0 0 0 0 0 0 
0 4368 188682 1482416 4160120 4899264 2511376 536384 41328 800 1 0 0 0 0 
0 11440 1482416 26232784 139089120 291102560 265085216 106311200 17712368 1048560 15232 16 0 0 0 
0 11440 4160120 139089120 216926039 947184153 3...

result:

ok 225 tokens

Test #5:

score: 0

Accepted

time: 0ms

memory: 7536kb

input:

16 1006729121

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 680 6188 19448 24310 12376 2380 136 1 0 0 0 0 0 0 0 
0 6188 305150 2867696 9916066 14924539 10288876 3196000 410329 17748 153 0 0 0 0 0 
0 19448 2867696 59852036 387206263 15304436 216863763 683915984 173666645 18275272 650641 4828 1 0 0 0 
0 24310 9916066 38720626...

result:

ok 256 tokens

Subtask #3:

score: 25

Accepted

Test #6:

score: 25

Accepted

time: 54ms

memory: 22968kb

input:

36 1003299797

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 7770 435897 10295472 124403620 854992152 552567909 334501587 855871755 616535351 836177106 87288018 849183199 348330136 38608020 2324784 66045 666 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 435897 133844910 939232742 752696285 94...

result:

ok 1296 tokens

Test #7:

score: 0

Accepted

time: 64ms

memory: 24452kb

input:

37 1009736899

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 8436 501942 12620256 163011640 193585389 366265801 325233075 508510208 4472335 508510208 325233075 366265801 193585389 163011640 12620256 501942 8436 38 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 501942 164674938 380061172 7953...

result:

ok 1369 tokens

Test #8:

score: 0

Accepted

time: 72ms

memory: 25804kb

input:

38 1002064493

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 9139 575757 15380937 211915132 673991551 105909500 89228335 917893160 782878886 231145424 634874749 53537001 904603957 635745396 61523748 3262623 82251 741 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 575757 201514950 2661126...

result:

ok 1444 tokens

Test #9:

score: 0

Accepted

time: 93ms

memory: 27320kb

input:

39 1000696681

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 9880 658008 18643560 273438880 310408078 24862708 197477816 671070872 191143189 191143189 671070872 197477816 24862708 310408078 273438880 18643560 658008 9880 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 658008 24533645...

result:

ok 1521 tokens

Test #10:

score: 0

Accepted

time: 103ms

memory: 29016kb

input:

40 1002813283

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 10660 749398 22481940 350343565 151022119 572250549 255038067 159674717 979042431 374977376 547170717 790491840 141687815 878961939 118286125 95548245 4496388 101270 820 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 7493...

result:

ok 1600 tokens

Subtask #4:

score: 0

Runtime Error

Test #11:

score: 0

Runtime Error

input:

96 1005401729

output:

result:

Subtask #5:

score: 0

Runtime Error

Test #16:

score: 0

Runtime Error

input:

496 1005266363