結果
問題 | No.502 階乗を計算するだけ |
ユーザー |
![]() |
提出日時 | 2020-05-20 00:32:38 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 597 ms / 1,000 ms |
コード長 | 5,455 bytes |
コンパイル時間 | 20,662 ms |
コンパイル使用メモリ | 308,752 KB |
最終ジャッジ日時 | 2025-01-10 13:16:15 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 52 |
ソースコード
#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;}