QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245959#7759. Permutation Counting 2grass8cow100 ✓1175ms21052kbC++143.1kb2023-11-10 14:49:492023-11-10 14:49:50

Judging History

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

  • [2023-11-10 14:49:50]
  • 评测
  • 测评结果:100
  • 用时:1175ms
  • 内存:21052kb
  • [2023-11-10 14:49:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n;
int mod;
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
typedef unsigned long long ull;
namespace FM{
	typedef __uint128_t L;
	struct FastMod{
		ull b,m;
		FastMod(ull b):b(b),m(ull((L(1)<<64)/b)){}
		ull reduce(ull a){ull q=(ull)((L(m)*a)>>64),r=a-q*b;return r>=b?r-b:r;}
	};
	FastMod F(2);
}
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=FM::F.reduce(1ull*x*o.x),*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}
void initmod(){scanf("%d",&mod),FM::F=FM::FastMod(mod);}
vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}
////////////////////////////////////////////////////////////////////////////////
modint f[510][510],g[510][510],dp[510][510],h[510][510],fz[510][510],O[510][510];
int main(){
	scanf("%d",&n);initmod();
	initC(1000000);
	//freopen("b.out","w",stdout);
    O[0][0]=1;
    for(int i=1;i<=n;i++){
        O[i][0]=1;
        for(int j=1;j<=i;j++)O[i][j]=O[i-1][j-1]+O[i-1][j];
    }
	for(int d=1;d<=n;d++){
		for(int i=1;i<=n;i++)for(int j=0;j<i;j++)
		f[i][d]+=sign(j)*O[i][j]*C(n+(i-j)*d-1,(i-j)*d-1);
	}
	for(int a=1;a<=n;a++)for(int b=1;b<=n;b++)for(int c=0;c<b;c++)
	g[n-a][n-b]+=sign(c)*f[a][b-c]*O[b][c];
	for(int a=0;a<n;a++)for(int b=a;b<n;b++)for(int d=0;d<n;d++)
	fz[a][d]+=sign(b-a)*g[b][d]*O[b][a];
	for(int a=0;a<n;a++)for(int c=0;c<n;c++)for(int d=c;d<n;d++)
	h[a][c]+=sign(d-c)*fz[a][d]*O[d][c];
	/*for(int a=0;a<n;a++)for(int b=a;b<n;b++)for(int c=0;c<n;c++)for(int d=c;d<n;d++)
	(h[a][c]+=(((b-a+d-c)&1)?-1ll:1ll)*g[b][d]*C(b,a)%mod*C(d,c)%mod)%=mod;*/
	for(int a=0;a<n;a++)for(int c=0;c<n;c++)printf("%d%c",h[a][c].x,(c==n-1)?'\n':' ');
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 7ms
memory: 20964kb

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

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

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

result:

ok 196 tokens

Test #4:

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

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

result:

ok 225 tokens

Test #5:

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

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

result:

ok 256 tokens

Subtask #3:

score: 25
Accepted

Test #6:

score: 25
Accepted
time: 7ms
memory: 20884kb

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

result:

ok 1296 tokens

Test #7:

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

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

result:

ok 1369 tokens

Test #8:

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

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

result:

ok 1444 tokens

Test #9:

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

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

result:

ok 1521 tokens

Test #10:

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

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

result:

ok 1600 tokens

Subtask #4:

score: 25
Accepted

Test #11:

score: 25
Accepted
time: 15ms
memory: 20928kb

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

result:

ok 9216 tokens

Test #12:

score: 0
Accepted
time: 15ms
memory: 21000kb

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

result:

ok 9409 tokens

Test #13:

score: 0
Accepted
time: 20ms
memory: 20888kb

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

result:

ok 9604 tokens

Test #14:

score: 0
Accepted
time: 16ms
memory: 21040kb

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

result:

ok 9801 tokens

Test #15:

score: 0
Accepted
time: 21ms
memory: 21036kb

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

result:

ok 10000 tokens

Subtask #5:

score: 25
Accepted

Test #16:

score: 25
Accepted
time: 1136ms
memory: 21000kb

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: 1153ms
memory: 20984kb

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: 1151ms
memory: 21044kb

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: 1161ms
memory: 21052kb

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: 1175ms
memory: 21000kb

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