結果
問題 | No.271 next_permutation (2) |
ユーザー | LayCurse |
提出日時 | 2015-08-22 00:19:55 |
言語 | C++11 (gcc 11.4.0) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 8,469 bytes |
コンパイル時間 | 1,437 ms |
コンパイル使用メモリ | 163,740 KB |
実行使用メモリ | 1,444,680 KB |
最終ジャッジ日時 | 2024-10-08 12:48:49 |
合計ジャッジ時間 | 8,435 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | MLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
コンパイルメッセージ
main.cpp: In member function ‘unsigned int mint::setmod(unsigned int)’: main.cpp:41:675: warning: no return statement in function returning non-void [-Wreturn-type] 41 | unsigned setmod(unsigned m){int i;unsigned t;W=32;md=m;R=(1ULL<<W)%md;RR=(ull)R*R%md;switch(m){case 104857601:Rinv=2560000;mdninv=104857599;break;case 998244353:Rinv=232013824;mdninv=998244351;break;case 1000000007:Rinv=518424770;mdninv=2226617417U;break;case 1000000009:Rinv=171601999;mdninv=737024967;break;case 1004535809:Rinv=234947584;mdninv=1004535807;break;case 1007681537:Rinv=236421376;mdninv=1007681535;break;case 1012924417:Rinv=238887936;mdninv=1012924415;break;case 1045430273:Rinv=254466304;mdninv=1045430271;break;case 1051721729:Rinv=257538304;mdninv=1051721727;break;default:Rinv=get_inv(R,md);mdninv=0;t=0;rep(i,W){if(t%2==0)t+=md,mdninv|=(1U<<i);t/=2;}}} | ^ main.cpp: In function ‘void reader(double*)’: main.cpp:15:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 15 | void reader(double *x){scanf("%lf",x);} | ~~~~~^~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; #define REP(i,a,b) for(i=a;i<b;i++) #define rep(i,n) REP(i,0,n) #define mygc(c) (c)=getchar_unlocked() #define mypc(c) putchar_unlocked(c) #define ll long long #define ull unsigned ll void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);} void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);} void reader(double *x){scanf("%lf",x);} int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;} template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);} template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);} template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);} void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);} void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);} void writer(double x, char c){printf("%.15f",x);mypc(c);} void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);} void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);} template<class T> void writerLn(T x){writer(x,'\n');} template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');} template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');} template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');} char memarr[17000000]; void *mem = memarr; #define MD 1000000007 int get_inv(ll a, int md){ll t=a,s=md,u=1,v=0,e;while(s){e=t/s;t-=e*s;u-=e*v;swap(t,s);swap(u,v);}if(u<0)u+=md;return u;} struct mint{ static unsigned md, W, R, Rinv, mdninv, RR; unsigned val; mint(){}mint(int a){val=mulR(a);}mint(unsigned a){val=mulR(a);}mint(ll a){val=mulR(a);}mint(ull a){val=mulR(a);} unsigned setmod(unsigned m){int i;unsigned t;W=32;md=m;R=(1ULL<<W)%md;RR=(ull)R*R%md;switch(m){case 104857601:Rinv=2560000;mdninv=104857599;break;case 998244353:Rinv=232013824;mdninv=998244351;break;case 1000000007:Rinv=518424770;mdninv=2226617417U;break;case 1000000009:Rinv=171601999;mdninv=737024967;break;case 1004535809:Rinv=234947584;mdninv=1004535807;break;case 1007681537:Rinv=236421376;mdninv=1007681535;break;case 1012924417:Rinv=238887936;mdninv=1012924415;break;case 1045430273:Rinv=254466304;mdninv=1045430271;break;case 1051721729:Rinv=257538304;mdninv=1051721727;break;default:Rinv=get_inv(R,md);mdninv=0;t=0;rep(i,W){if(t%2==0)t+=md,mdninv|=(1U<<i);t/=2;}}} unsigned mulR(unsigned a){return(ull)a*R%md;}unsigned mulR(int a){if(a<0)a=a%md+md;return mulR((unsigned)a);}unsigned mulR(ull a){return mulR((unsigned)(a%md));}unsigned mulR(ll a){if(a<0)a=a%md+md;return mulR((unsigned)a);} unsigned reduce(unsigned T){unsigned m=T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}unsigned reduce(ull T){unsigned m=(unsigned)T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;} unsigned get(){return reduce(val);} mint&operator+=(mint a){val+=a.val;if(val>=md)val-=md;return*this;}mint&operator-=(mint a){if(val<a.val)val=val+md-a.val;else val-=a.val;return*this;}mint&operator*=(mint a){val=reduce((ull)val*a.val);return*this;}mint&operator/=(mint a){return*this*=a.inverse();} mint operator+(mint a){return mint(*this)+=a;}mint operator-(mint a){return mint(*this)-=a;}mint operator*(mint a){return mint(*this)*=a;}mint operator/(mint a){return mint(*this)/=a;} mint operator+(int a){return mint(*this)+=mint(a);}mint operator-(int a){return mint(*this)-=mint(a);}mint operator*(int a){return mint(*this)*=mint(a);}mint operator/(int a){return mint(*this)/=mint(a);} mint operator+(ll a){return mint(*this)+=mint(a);}mint operator-(ll a){return mint(*this)-=mint(a);}mint operator*(ll a){return mint(*this)*=mint(a);}mint operator/(ll a){return mint(*this)/=mint(a);} mint operator-(void){mint res;if(val)res.val=md-val;else res.val=0;return res;} operator bool(void){return val!=0;}operator int(void){return get();}operator ll(void){return get();} mint inverse(){int a=val,b=md,u=1,v=0,t;mint r;while(b){t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}if(u<0)u+=md;r.val=(ull)u*RR%md;return r;} mint pw(ull b){mint a(*this),r;r.val=R;while(b){if(b&1)r*=a;b>>=1;a*=a;}return r;} bool operator==(int a){return get()==a;} bool operator!=(int a){return get()!=a;} }; unsigned mint::md, mint::W, mint::R, mint::Rinv, mint::mdninv, mint::RR; mint operator+(int a, mint b){return mint(a)+=b;}mint operator-(int a, mint b){return mint(a)-=b;}mint operator*(int a, mint b){return mint(a)*=b;}mint operator/(int a, mint b){return mint(a)/=b;} mint operator+(ll a, mint b){return mint(a)+=b;}mint operator-(ll a, mint b){return mint(a)-=b;}mint operator*(ll a, mint b){return mint(a)*=b;}mint operator/(ll a, mint b){return mint(a)/=b;} mint mval[10000], minv[10000]; void mint_init(int md=MD, mint val[]=mval, int vals=10000, mint inv[]=minv, int invs=10000){int i;val[0].setmod(md);val[0].val=0;REP(i,1,vals){val[i].val=val[i-1].val+mint::R;if(val[i].val >=md)val[i].val-=md;}inv[1].val=1;REP(i,2,invs){inv[i].val=md-((ll)(md/i)*inv[md%i].val%md);}REP(i,1,invs)inv[i].val=(ull)inv[i].val*mint::R%md;} template<class T> struct fenwick{ int size, memory; T *data; void malloc(int mem){memory=mem;data=(T*)std::malloc(sizeof(T)*mem);} void *malloc(int mem, void *workMemory){memory=mem;data=(T*)workMemory;return (void*)(data+mem);} void free(void){memory=0;free(data);} void init(int N){size=N;memset(data,0,sizeof(T)*N);} void add(int k, T val){while(k<size)data[k]+=val,k|=k+1;} T get(int k){T res=0;while(k>=0)res+=data[k],k=(k&(k+1))-1;return res;} T range(int a, int b){if(b==-1)b=size-1;return get(b)-get(a-1);} int kth(T k){int i=0,j=size,c;T v;while(i<j){c=(i+j)/2;v=get(c);if(v<=k)i=c+1;else j=c;}return i==size?-1:i;} }; void intReverse(int d[],int size){ int a=0, b=size-1, t; while(a<b) t=d[a], d[a]=d[b], d[b]=t, a++, b--; } int intNextPermutation(int d[],int size){ int i,j,k; for(k=size-2;k>=0;k--) if(d[k]<d[k+1]) break; if(k<0){intReverse(d,size); return 0;} for(i=size-1;;i--) if(d[i]>d[k]) break; j=d[i], d[i]=d[k], d[k]=j; intReverse(d+k+1, size-k-1); return i; } int N; ll K; int P[100010]; ll fact[100010]; ll sa[100010], sum[100010]; int main(){ int i, j, k, m; fenwick<int> t; mint res = 0; ll tmp; mint_init(); reader(&N,&K); rep(i,N) reader(P+i), P[i]--; if(0){ int i, j, k; int PP[100]; rep(i,N) PP[i] = P[i]; int res = 0; rep(k,K){ rep(i,N) REP(j,i+1,N) if(PP[i] > PP[j]) res++; next_permutation(PP, PP+N); } writerLn(res); } fact[0] = 1; REP(i,1,N+10){ if(fact[i-1] > 3000000000000000000LL / i) fact[i] = 3000000000000000000LL; else fact[i] = fact[i-1] * i; } if(K >= fact[N]){ tmp = K / fact[N]; K -= fact[N] * tmp; res += mint((ull)tmp) * (mint(N) * mint(N-1) * minv[4] * mint((ull)fact[N])); } t.malloc(N); t.init(N); rep(i,N) t.add(i,1); rep(i,N){ sa[i] = t.get(P[i]-1); t.add(P[i], -1); } sum[0] = 0; rep(i,N) sum[i+1] = sum[i] + sa[i]; while(K){ for(i=N-1;i;i--){ m = N-i; if(P[i-1] > P[i]) break; if(fact[m+1] > K) break; } K -= fact[m]; res += mint((ull)fact[m]) * mint((ull)sum[N-m]) + mint(m) * mint(m-1) * minv[4] * mint((ull)fact[m]); reverse(P+N-m, P+N); i = intNextPermutation(P, N); if(i < N-50){ t.init(N); rep(i,N) t.add(i,1); rep(i,N){ sa[i] = t.get(P[i]-1); t.add(P[i], -1); } sum[0] = 0; rep(i,N) sum[i+1] = sum[i] + sa[i]; } else { i = max(0, i-100); REP(j,i,N){ sa[j] = 0; REP(k,j+1,N) if(P[j] > P[k]) sa[j]++; sum[j+1] = sum[j] + sa[j]; } } } writerLn((int)res); return 0; }