QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253586 | #7759. Permutation Counting 2 | Crysfly | 100 ✓ | 2197ms | 9156kb | C++17 | 3.8kb | 2023-11-17 09:20:30 | 2023-11-17 09:20:31 |
Judging History
answer
// what is matter? never mind.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#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
//#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
int mod;
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(){mod=read(),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);}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 1000005
#define inf 0x3f3f3f3f
int n;
modint f[505][505],res[505][505],ans[505][505];
modint F(int n,int m){
// n balls , m pockets
return C(n+m-1,m-1);
}
void work(int t){
// memset(f,0,sizeof f);
// f[0][0]=1;
// For(i,1,n){
// For(j,0,n-1)
// if(f[i-1][j].x){
// For(k,1,n-j)
// f[i][j+k]+=f[i-1][j]*F(k,t);
// }
// res[t][i]=f[i][n];
// }
For(i,1,n)
res[t][i]=F(n,t*i);
}
signed main()
{
n=read(),initmod(); initC(505);
For(i,1,n)work(i);
For(t,1,n){
Rep(i,n,1)
For(j,1,i-1)
res[i][t]+=res[j][t]*C(i,j)*sign(i-j);
}
For(t,1,n){
Rep(i,n,1)
For(j,1,i-1)
res[t][i]+=res[t][j]*C(i,j)*sign(i-j);
}
// For(t,1,n){
// For(i,1,n)cout<<res[i][t].x<<" ";
// cout<<"\n";
// }
For(i,1,n)For(j,1,n)ans[n-i][n-j]=res[i][j];
For(t,0,n-1){
For(i,0,n-1)
For(j,i+1,n)
ans[t][i]+=ans[t][j]*C(j,i)*sign(j-i);
}
For(t,0,n-1){
For(i,0,n-1)
For(j,i+1,n)
ans[i][t]+=ans[j][t]*C(j,i)*sign(j-i);
}
// memset(res,0,sizeof res);
// For(i,0,n-1)
// For(j,0,n-1)
// For(ii,i,)For(jj,0,j)
// res[i][j]+=ans[ii][jj]*C(i,ii)*C(j,jj)*sign(i-ii+j-jj);
For(t,0,n-1){
For(i,0,n-1)cout<<ans[i][t].x<<" ";
cout<<"\n";
}
return 0;
}
/*
200 1000000007
1 0 0
1 2 3
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 6568kb
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: 0ms
memory: 6572kb
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: 0ms
memory: 6508kb
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: 6580kb
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: 2ms
memory: 6588kb
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: 2ms
memory: 6612kb
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: 2ms
memory: 6604kb
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: 2ms
memory: 6820kb
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: 0ms
memory: 6592kb
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: 2ms
memory: 6792kb
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: 14ms
memory: 6696kb
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: 18ms
memory: 6948kb
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: 19ms
memory: 6628kb
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: 19ms
memory: 6720kb
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: 15ms
memory: 6584kb
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: 2149ms
memory: 9156kb
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: 2159ms
memory: 9140kb
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: 2175ms
memory: 9152kb
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: 2171ms
memory: 9084kb
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: 2197ms
memory: 9148kb
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