QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#296367#7759. Permutation Counting 2honglan0301100 ✓583ms8184kbC++175.9kb2024-01-02 20:13:562024-01-02 20:13:58

Judging History

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

  • [2024-01-02 20:13:58]
  • 评测
  • 测评结果:100
  • 用时:583ms
  • 内存:8184kb
  • [2024-01-02 20:13:56]
  • 提交

answer

/*
  author: honglan0301
  Sexy_goodier _ xiaoqing
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <cmath>
#include <random>
#include <set>
#include <bitset>
#include <assert.h>
using namespace std;

//namespace Fread{const int SIZE=1<<20;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return*S++;}}using namespace Fread;namespace Fwrite{const int SIZE=1<<20;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;}using namespace Fwrite;
//#define getchar Fread::getchar
//#define putchar Fwrite::putchar

namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){x=0;short f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();x*=f;return*this;}Reader&operator>>(double&x){x=0;double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){x=0;long double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){x=0;__float128 t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(char&c){c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(string&str){str.clear();char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{const int Setprecision=6;typedef int mxdouble;template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return*this;}if(x<0)putchar('-'),x=-x;static short sta[40];short top=0;while(x>0)sta[++top]=x%10,x/=10;while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl//;fflush(stdout)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
mt19937 rnd(time(0));
mt19937_64 rndl(time(0));

int n,mod,jc[300005],ny[300005],dp[505][505],c[505][505];

int ksm(ll x,int k) {ll na=1; for(int i=1;i<=k;i<<=1) {if(i&k) na=na*x%mod; x=x*x%mod;} return na;}
#define c(x,y) (ll)jc[x]%mod*ny[y]%mod*ny[(x)-(y)]%mod
void init()
{
	jc[0]=1; for(int i=1;i<=300000;i++) jc[i]=(ll)jc[i-1]*i%mod;
	ny[300000]=ksm(jc[300000],mod-2); for(int i=299999;i>=0;i--) ny[i]=(ll)ny[i+1]*(i+1)%mod;
	c[0][0]=1; for(int i=1;i<=500;i++) {c[i][0]=1; for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}
}

signed main()
{
	cin>>n>>mod; init();
	for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++) dp[i][j]=c(i*j+n-1,n);
	for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++) for(int p=1;p<j;p++) dp[i][j]-=(ll)dp[i][p]*c[j][p]%mod,(dp[i][j]<0)?(dp[i][j]+=mod):0;
	for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++) for(int p=1;p<i;p++) dp[i][j]-=(ll)dp[p][j]*c[i][p]%mod,(dp[i][j]<0)?(dp[i][j]+=mod):0;
	for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++) for(int p=1;p<j;p++) dp[i][j]-=(ll)dp[i][p]*c[n-p][j-p]%mod,(dp[i][j]<0)?(dp[i][j]+=mod):0;
	for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++) for(int p=1;p<i;p++) dp[i][j]-=(ll)dp[p][j]*c[n-p][i-p]%mod,(dp[i][j]<0)?(dp[i][j]+=mod):0;
	for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++) dp[n-i+1][n-j+1]=dp[i][j];//
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) cout<<dp[n-i+1][n-j+1]<<" "; cout<<endl;
	}
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 5ms
memory: 6980kb

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: 6ms
memory: 7700kb

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: 5ms
memory: 7236kb

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: 2ms
memory: 7784kb

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: 5ms
memory: 7396kb

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: 5ms
memory: 8184kb

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: 6ms
memory: 7956kb

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: 6ms
memory: 8032kb

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: 6ms
memory: 8036kb

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

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: 25
Accepted

Test #11:

score: 25
Accepted
time: 10ms
memory: 8024kb

input:

96 1005401729

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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 147440 64446024 781420036 468430311 27733626 62151757 454795566 711626792 885805006 401110492 711423106 3...

result:

ok 9216 tokens

Test #12:

score: 0
Accepted
time: 7ms
memory: 8168kb

input:

97 1003022927

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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 152096 67910864 795115101 924546504 230011659 577127906 564913191 11843263 171607987 697964156 4314087 ...

result:

ok 9409 tokens

Test #13:

score: 0
Accepted
time: 5ms
memory: 8184kb

input:

98 1000259233

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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 156849 71523144 883402282 582472554 858367843 730708960 476781508 806308877 286962083 221796390 32768...

result:

ok 9604 tokens

Test #14:

score: 0
Accepted
time: 11ms
memory: 8032kb

input:

99 1000444889

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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 161700 75287520 442576 386074411 823487426 504618380 971268883 734797176 388493421 848753352 857480...

result:

ok 9801 tokens

Test #15:

score: 0
Accepted
time: 7ms
memory: 8184kb

input:

100 1008746839

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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 166650 79208745 50916937 213745970 953400361 882774939 595265332 362179793 339853992 820776686 20...

result:

ok 10000 tokens

Subtask #5:

score: 25
Accepted

Test #16:

score: 25
Accepted
time: 561ms
memory: 8116kb

input:

496 1005266363

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 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 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 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 ...

result:

ok 246016 tokens

Test #17:

score: 0
Accepted
time: 571ms
memory: 8024kb

input:

497 1000331767

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 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 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 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 ...

result:

ok 247009 tokens

Test #18:

score: 0
Accepted
time: 572ms
memory: 8028kb

input:

498 1000148759

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 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 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 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 ...

result:

ok 248004 tokens

Test #19:

score: 0
Accepted
time: 576ms
memory: 7960kb

input:

499 1000176851

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 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 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 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 ...

result:

ok 249001 tokens

Test #20:

score: 0
Accepted
time: 583ms
memory: 7912kb

input:

500 1002873259

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 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 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 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 ...

result:

ok 250000 tokens