#483902 (C++17) No.502 階乗を計算するだけ

提出ソース

結果

問題	No.502 階乗を計算するだけ
ユーザー	αmusement
提出日時	2020-05-20 00:32:38
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	429 ms / 1,000 ms
コード長	5,455 bytes
コンパイル時間	4,311 ms
コンパイル使用メモリ	249,912 KB
実行使用メモリ	7,080 KB
最終ジャッジ日時	2024-04-27 03:11:51
合計ジャッジ時間	9,391 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	1 ms 6,944 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	1 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	1 ms 6,940 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	1 ms 6,944 KB
testcase_19	AC	1 ms 6,940 KB
testcase_20	AC	1 ms 6,944 KB
testcase_21	AC	1 ms 6,940 KB
testcase_22	AC	10 ms 6,940 KB
testcase_23	AC	6 ms 6,940 KB
testcase_24	AC	10 ms 6,940 KB
testcase_25	AC	3 ms 6,940 KB
testcase_26	AC	6 ms 6,940 KB
testcase_27	AC	5 ms 6,944 KB
testcase_28	AC	5 ms 6,944 KB
testcase_29	AC	5 ms 6,940 KB
testcase_30	AC	10 ms 6,944 KB
testcase_31	AC	5 ms 6,944 KB
testcase_32	AC	416 ms 6,944 KB
testcase_33	AC	415 ms 7,032 KB
testcase_34	AC	197 ms 6,944 KB
testcase_35	AC	193 ms 6,944 KB
testcase_36	AC	416 ms 6,940 KB
testcase_37	AC	405 ms 6,940 KB
testcase_38	AC	423 ms 7,080 KB
testcase_39	AC	420 ms 6,944 KB
testcase_40	AC	93 ms 6,940 KB
testcase_41	AC	429 ms 6,984 KB
testcase_42	AC	2 ms 6,944 KB
testcase_43	AC	2 ms 6,944 KB
testcase_44	AC	1 ms 6,944 KB
testcase_45	AC	1 ms 6,940 KB
testcase_46	AC	1 ms 6,944 KB
testcase_47	AC	2 ms 6,940 KB
testcase_48	AC	1 ms 6,944 KB
testcase_49	AC	1 ms 6,940 KB
testcase_50	AC	1 ms 6,940 KB
testcase_51	AC	1 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC target("avx")
//#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define DB double
#define ST string
#define BS bitset
#define PA pair<LL,LL>
#define VE vector
#define VL vector<LL>
#define VP vector<pair<LL,LL>>
#define VVL vector<vector<LL>>
#define PQ priority_queue
#define PQS priority_queue<LL,vector<LL>,greater<LL>>
#define PB push_back
#define POB pop_back
#define PF push_front
#define POF pop_front
#define EB emplace_back
#define MP make_pair
#define TS to_string
#define TU to_ullong
#define BPL __builtin_popcountll
#define FOR(i,a,n) for(i=a;i<n;i++)
#define FORR(i,a,n) for(i=n-1;i>=a;i--)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) FORR(i,0,n)
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define UB(a,n) *upper_bound(ALL(a),n)
#define LB(a,n) *lower_bound(ALL(a),n)
#define INF 1145141919810364364
#define PI 3.14159265358979
#define MOD 1000000007
//#define MOD 998244353
#define ERR 0.00000001
#define NUM 200010
#define FAST cin.tie(0);ios::sync_with_stdio(false)

void Yn(LL a){if(a)printf("Yes\n");else printf("No\n");}
void YN(LL a){if(a)printf("YES\n");else printf("NO\n");}
LL pwmn(LL a,LL n){LL ans=1;while(ans<a)ans*=n;return ans;}
LL dig(LL n){LL ret=0;while(n)n/=10,ret++;return ret;}
LL LBn(VL &v,LL a){LL mx=v.size(),mn=-1,md;while(mx-mn>1){md=(mx+mn)/2;if(v[md]<a)mn=md;else mx=md;}return mx;}
LL GCD(LL a,LL b){LL c=1,tmp=max(a,b);b=min(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
LL LCM(LL a,LL b){return a*b/GCD(a,b);}
int lcmp(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return 1;if(*(LL*)a<*(LL*)b)return -1;return 0;}
int lcmpr(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return -1;if(*(LL*)a<*(LL*)b)return 1;return 0;}
int ccmp(const void* a,const void* b){return *(char*)a-*(char*)b;}
int ccmpr(const void* a,const void* b){return *(char*)b-*(char*)a;}
int scmp(const void* a,const void* b){return strcmp((char*)a,(char*)b);}
int scmpr(const void* a,const void* b){return strcmp((char*)b,(char*)a);}
LL cmod(LL a,LL m){if(a%m<0)return a%m+abs(m);else return a%m;}
LL DIV(LL a,LL d,LL m){LL l=m,x=1,y=0,k;while(l){k=d/l;d-=k*l;swap(l,d);x-=k*y;swap(x,y);}return cmod(a*cmod(x,m),m);}
LL POW(LL a,LL n,LL m){LL ans=1;while(n>0){if(n&1)ans=ans*a%m;a=a*a%m;n>>=1;}return ans;}
LL fact[NUM],finv[NUM],inv[NUM];
void comi(){LL i;fact[0]=fact[1]=1;finv[0]=finv[1]=1;inv[1]=1;FOR(i,2,NUM){fact[i]=fact[i-1]*i%MOD;inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}}
LL com(LL n,LL k){if(n<k||n<0||k<0)return 0;return fact[n]*(finv[k]*finv[n-k]%MOD)%MOD;}
bool cmps(pair<LL,LL> a,pair<LL,LL> b){if(a.second!=b.second)return a.second<b.second;return a.first<b.first;}
template<typename T>bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

template<int mod,int root>struct NTT{
	int getmod()const{return mod;};
	void ntt(VL &f,int inv){int n=f.size(),i=0,j,k,r=(int)POW(root,(mod-1)/n,mod);LL a,b,x,z;if(inv==-1)r=(int)DIV(1,r,mod);FOR(j,1,n-1){for(k=n>>1;k>(i^=k);k>>=1);if(j<i)swap(f[i],f[j]);}for(i=1;i<n;i<<=1){x=1,z=POW(r,n/(i*2),mod);rep(j,i){for(k=j;k<n;k+=i*2){a=f[k],b=f[k+i]*x%mod;f[k]=a+b,f[k+i]=a-b;if(f[k]>=mod)f[k]-=mod;if(f[k+i]<0)f[k+i]+=mod;}x=x*z%mod;}}}
	VL conv(VL f,VL g){int s=f.size()+g.size(),n=pwmn(s,2),d=DIV(1,n,mod),i;f.resize(n);g.resize(n);ntt(f,1);ntt(g,1);rep(i,n)f[i]*=g[i],f[i]%=mod;ntt(f,-1);rep(i,n)f[i]*=d,f[i]%=mod;f.resize(s-1);return f;}
};
VL AMC(VL f,VL g,int m){NTT<167772161,3> n1;NTT<469762049,3> n2;NTT<1224736769,3> n3;for(auto &i:f)i%=m;for(auto &i:g)i%=m;VL p=n1.conv(f,g),q=n2.conv(f,g),r=n3.conv(f,g),ret(p.size());int i;LL t1,t2,x,m1=n1.getmod(),m2=n2.getmod(),m3=n3.getmod();LL i1_2=DIV(1,m1,m2),i12_3=DIV(1,m1*m2,m3),m12_m=m1*m2%m;rep(i,p.size()){t1=(q[i]-p[i])*i1_2%m2;if(t1<0)t1+=m2;t2=(r[i]-(p[i]+m1*t1)%m3)*i12_3%m3;if(t2<0)t2+=m3;x=(p[i]+m1*t1+m12_m*t2)%m;ret[i]=x;}return ret;}
template<int mod>
struct FAC{
	LL sq,sqi,fac;VL inv;
	FAC(LL n){if(n<=0){fac=1;return;}if(n>=mod){fac=0;return;}LL i,a;sq=sqrt(n),sqi=DIV(1,sq,mod),fac=1;inv.PB(1);rep(i,sq){a=inv[i]*DIV(1,i+1,mod)%mod;inv.PB(a);}VL v=calc(sq);rep(i,sq)(fac*=v[i])%=mod;FOR(i,sq*sq+1,n+1)(fac*=i)%=mod;}
	VL fac_sh(VL f,LL d){LL i,a,n=f.size(),s=n*2-1,m=d*sqi%mod,k=n-1,z=-1,fl=0;VL b=f,g(s);rep(i,n){a=inv[i]*inv[k-i]%mod;if((k-i)&1)a=-a+mod;(f[i]*=a)%=mod;}rep(i,s){g[i]=m-k+i;if(g[i]==0)g[i]=1,z=i;if(g[i]<0)g[i]+=mod;}rep(i,s-1)(g[i+1]*=g[i])%=mod;a=DIV(1,g[s-1],mod);repr(i,s-1){g[i+1]=(a*g[i])%mod;if(m-k+i+1==0)continue;(a*=(m-k+i+1))%=mod;if(a<0)a+=mod;}
	g[0]=a;if(z>=0)g[z]=0;VL h=AMC(f,g,mod);h=VL(h.begin()+k,h.begin()+n+k);a=1;repr(i,n){if(m-i==0){fl=1;continue;}(a*=m-i)%=mod;if(a<0)a+=mod;}rep(i,n){if(fl)h[i]=b[i+k-z];else (h[i]*=a)%=mod;if(m+i+1==0)(a*=g[i])%=mod,fl=1;else if(g[i]==0)(a*=(m+i+1))%=mod,fl=0;else (a*=(g[i]*(m+i+1))%mod)%=mod;if(a<0)a+=mod;}return h;}
	VL calc(LL n){if(n==1)return {1,1+sq};LL a=1,i,d=n>>1;VL v=calc(d),v1=fac_sh(v,d),v2=fac_sh(v,d*sq),v3=fac_sh(v,d*sq+d);rep(i,d+1)(v[i]*=v1[i])%=mod;rep(i,d)v.PB(v2[i+1]*v3[i+1]%mod);if(n&1){rep(i,n){(v[i]*=(n+sq*i)%mod)%=mod;(a*=(n*sq+i+1)%mod)%=mod;}v.PB(a);}return v;}
};

int main(){
	FAST;
	LL n;
  cin>>n;
  FAC<MOD> f(n);
  cout<<f.fac<<endl;
}

yukicoder

結果

テストケース

ソースコード