結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
![]() |
提出日時 | 2023-07-19 14:54:02 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 417 ms / 2,000 ms |
コード長 | 12,892 bytes |
コンパイル時間 | 5,138 ms |
コンパイル使用メモリ | 185,828 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-19 13:49:32 |
合計ジャッジ時間 | 22,672 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;template<int mod>istream &operator>>(istream &is,static_modint<mod> &a){long long b;is>>b;a=b;return is;}template<int mod>ostream &operator<<(ostream &os,const static_modint<mod> &a){os<<a.val();return os;}istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;}ostream &operator<<(ostream &os,const modint &a){os<<a.val();return os;}#endifusing ll=long long;using ull=unsigned long long;using P=pair<ll,ll>;template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}template<typename T> ostream &operator<<(ostream &os,const vector<T> &a){cout<<'{';for(int i=0;i<a.size();i++){cout<<a[i];if(i+1!=a.size())cout<<',';};cout<<'}';return os;}template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}#define reps(i,a,n) for(int i=(a);i<(n);i++)#define rep(i,n) reps(i,0,n)#define all(x) x.begin(),x.end()#define pcnt(x) __builtin_popcount(x)ll myceil(ll a,ll b){return (a+b-1)/b;}template<typename T1,typename ...T2>void debug(const T1& x,const T2& ...y){#ifdef LOCALcout<<x;((cout<<' '<<y),...);cout<<'\n';#endif}void SOLVE();int main(){ios::sync_with_stdio(false);cin.tie(nullptr);#ifdef LOCALclock_t start=clock();#endifint testcase=1;cin>>testcase;for(int i=0;i<testcase;i++){SOLVE();}#ifdef LOCALcout<<"time:";cout<<(clock()-start)/1000;cout<<"ms\n";#endif}constexpr int primitive_root(int x){if(x==998244353)return 3;return -1;}constexpr int countr_zero(unsigned int n){int ret=0;while(!(n&(1<<ret)))ret++;return ret;}template<typename T>struct ntt_root{static constexpr int rank2=countr_zero(T::mod()-1);int g=primitive_root(T::mod());array<T,rank2+1>root,invroot;array<T,max(0,rank2-1)>rate2,invrate2;array<T,max(0,rank2-2)>rate3,invrate3;ntt_root(){root[rank2]=T::raw(g).pow((T::mod())>>rank2);invroot[rank2]=root[rank2].inv();for(int i=rank2-1;i>=0;i--){root[i]=root[i+1]*root[i+1];invroot[i]=invroot[i+1]*invroot[i+1];}{T prod=1,invprod=1;rep(i,rank2-1){rate2[i]=root[i+2]*prod;invrate2[i]=invroot[i+2]*invprod;prod*=invroot[i+2];invprod*=root[i+2];}}{T prod=1,invprod=1;rep(i,rank2-2){rate3[i]=root[i+3]*prod;invrate3[i]=invroot[i+3]*invprod;prod*=invroot[i+3];invprod*=root[i+3];}}}};template<typename T>void dft(vector<T>&a){int n=a.size();static const ntt_root<T> r;int h=countr_zero(n);ull mod2=(ull)T::mod()*T::mod();int len=0;while(len<h){if(h-len==1){T rot=1;rep(s,1<<len){int of=s*2;T u=a[of],v=a[of+1]*rot;a[of]=u+v;a[of+1]=u-v;if(s+1!=1<<len)rot*=r.rate2[__builtin_ctz(~(unsigned int)s)];}len++;}else{int p=1<<(h-len-2);T rot=1,imag=r.root[2];rep(s,1<<len){T rot2=rot*rot,rot3=rot*rot2;int of=s<<(h-len);rep(i,p){ull a0=a[i+of].val(),a1=(ull)a[i+of+p].val()*rot.val(),a2=(ull)a[i+of+p*2].val()*rot2.val(),a3=(ull)a[i+of+p*3].val()*rot3.val();ull m=(ull)T(a1+mod2-a3).val()*imag.val();ull k=mod2-a2;a[i+of]=a0+a2+a1+a3;a[i+of+p]=a0+a2+(mod2*2-a1-a3);a[i+of+p*2]=a0+k+m;a[i+of+p*3]=a0+k+(mod2-m);}if(s+1!=1<<len)rot*=r.rate3[__builtin_ctz(~(unsigned int)s)];}len+=2;}}}template<typename T>void idft(vector<T>&a){int n=a.size();static const ntt_root<T> r;int h=countr_zero(n);ull mod2=(ull)T::mod()*T::mod();int len=h;while(len){if(len==1){int p=1<<(h-1);T rot=1;rep(i,p){T u=a[i],v=a[i+p];a[i]=u+v;a[i+p]=(ull)(u.val()-v.val()+T::mod())*rot.val();}len--;}else{int p=1<<(h-len);T rot=1,imag=r.invroot[2];rep(s,1<<(len-2)){T rot2=rot*rot,rot3=rot*rot2;int of=s<<(h-len+2);rep(i,p){ull a0=a[i+of].val(),a1=a[i+of+p].val(),a2=a[i+of+p*2].val(),a3=a[i+of+p*3].val();ull k=T((T::mod()+a2-a3)*imag.val()).val();a[i+of]=a0+a1+a2+a3;a[i+of+p]=(a0+T::mod()-a1+k)*rot.val();a[i+of+p*2]=(a0+a1+T::mod()*2-a2-a3)*rot2.val();a[i+of+p*3]=(a0+T::mod()*2-a1-k)*rot3.val();}if(s+1!=1<<(len-2))rot*=r.invrate3[countr_zero(~(unsigned int)s)];}len-=2;}}}template<typename T>vector<T>ntt_convolution(vector<T> a,vector<T> b){int n=a.size(),m=b.size(),s=n+m-1;if(min(n,m)<60){vector<T>ret(s,0);if(n<m)rep(i,m)rep(j,n)ret[i+j]+=a[j]*b[i];else rep(i,n)rep(j,m)ret[i+j]+=a[i]*b[j];return ret;}int z=1;while(z<=s)z*=2;a.resize(z,0);b.resize(z,0);dft(a),dft(b);vector<T>c(z);rep(i,z)c[i]=a[i]*b[i];idft(c);T g=T::raw(z).inv();rep(i,s)c[i]*=g;return {c.begin(),c.begin()+s};}template<typename T>vector<T> fps_inv(const vector<T> &a,int deg=-1){int n=a.size();if(deg==-1)deg=n;assert(a[0]!=T(0));vector<T> ret(deg);ret[0]=a[0].inv();for(int m=1;m<deg;m<<=1){vector<T> f(a.begin(),a.begin()+min(n,m*2));if(f.size()<m*2)f.resize(m*2,0);vector<T> g(ret);f.resize(m*2);dft(f);g.resize(m*2);dft(g);rep(i,m*2)f[i]*=g[i];idft(f);T inv=T::raw(m*2).inv();rep(i,m)f[i]=0;reps(i,m,m*2)f[i]*=inv;dft(f);rep(i,m*2)f[i]*=g[i];idft(f);rep(i,m*2)f[i]*=inv;reps(i,m,min(deg,m*2))ret[i]-=f[i];}return ret;}template<typename T>vector<T> fps_diff(const vector<T>&a){int n=a.size();vector<T>b(max(0,n-1));reps(i,1,n)b[i-1]=a[i]*i;return b;}template<typename T>vector<T> fps_integral(const vector<T>&a){int n=a.size();vector<T>b(n+1);b[0]=0;if(n)b[1]=1;reps(i,2,n+1)b[i]=-b[T::mod()%i]*(T::mod()/i);rep(i,n)b[i+1]*=a[i];return b;}template<typename T>vector<T> fps_log(const vector<T>&a,int deg=-1){int n=a.size();if(deg==-1)deg=n;vector<T>b=fps_integral(ntt_convolution(fps_diff(a),fps_inv(a,deg)));return {b.begin(),b.begin()+deg};}template<typename T>vector<T> fps_exp(const vector<T>&a,int deg=-1){assert(a.empty()||a[0]==0);int n=a.size();if(deg==-1)deg=n;vector<T>b{1};for(int m=1;m<deg;m*=2){vector<T>nxt=fps_log(b,m*2);rep(i,m*2)nxt[i]*=-1;rep(i,min(n,m*2))nxt[i]+=a[i];nxt[0]++;b=ntt_convolution(b,nxt);b.resize(m*2);}return {b.begin(),b.begin()+deg};}template<typename T>vector<T> fps_pow(vector<T> a,ll k,int deg=-1){int n=a.size();if(deg==-1)deg=n;if(k==0){vector<T>ret(deg,0);ret[0]=1;return ret;}int of=0;while(a[of]==0&&of!=n)of++;if(of==n)return vector<T>(deg,0);if(of!=0&&k>=deg)return vector<T>(deg,0);if(of*k>=deg)return vector<T>(deg,0);a.erase(a.begin(),a.begin()+of);n=a.size();T a0=a[0];T inv=a[0].inv();rep(i,n)a[i]*=inv;vector<T>lg=fps_log(a,deg);rep(i,deg)lg[i]*=k;vector<T>ep=fps_exp(lg,deg);T pw=a0.pow(k);rep(i,deg)ep[i]*=pw;vector<T>ret(deg,0);reps(i,of*k,deg)ret[i]=ep[i-of*k];return ret;}template<typename T>vector<T> fps_pow_sparse(const vector<T>&a,ll k,int deg=-1){int n=a.size();if(deg==-1)deg=n;vector<pair<int,T>>b;rep(i,n)if(a[i]!=0)b.emplace_back(i,a[i]);if(b.empty()){vector<T>ret(deg,0);if(k==0)ret[0]=1;return ret;}int of=b[0].first;T b0=b[0].second,inv=b0.inv();for(auto &i:b){i.first-=of;i.second*=inv;}b0=b0.pow(k);vector<T>ret(deg,0);ret[0]=1;rep(i,deg-1){T cu=0;for(auto [j,c]:b){if(i-j+1<0)continue;if(j==0)continue;cu-=c*ret[i-j+1]*(i-j+1);cu+=ret[i-j+1]*k*j*c;}ret[i+1]=cu/(i+1);}if(of){if(k>=deg||of*k>=deg)ret.assign(deg,0);else{ret.insert(ret.begin(),of*k,0);ret.resize(deg);}}for(auto &i:ret)i*=b0;return ret;}template<typename T>vector<T> fps_div_sparse(vector<T> a,const vector<T>&b,int deg=-1){int n=a.size(),m=b.size();if(deg==-1)deg=n;a.resize(deg,0);assert(b[0]!=0);vector<pair<int,T>>c;reps(i,1,m)if(b[i]!=0)c.emplace_back(i,b[i]);T v=b[0].inv();rep(i,deg){for(auto [j,e]:c){if(j>i)break;a[i]-=a[i-j]*e;}a[i]*=v;}return a;}template<typename T>inline vector<T> fps_inv_sparse(const vector<T>&a,int deg=-1){return fps_div_sparse({1},a,(deg==-1?a.size():deg));}template<typename T>vector<T>fps_fode_sparse(const vector<T>&a,const vector<T>&b){assert(a.size()==b.size());assert(a[0]==1);int n=a.size();vector<pair<int,T>>c,d;reps(i,1,n)if(a[i]!=0)c.emplace_back(i,a[i]);rep(i,n)if(b[i]!=0)d.emplace_back(i,b[i]);vector<T>f(n),df(n-1);f[0]=1;vector<T>inv(n);rep(i,n-1){T v=0;for(auto [j,x]:c){if(j>i)break;v+=x*df[i-j];}for(auto [j,x]:d){if(j>i)break;v+=x*f[i-j];}df[i]=-v;if(i==0)inv[1]=1;else inv[i+1]=-inv[T::mod()%(i+1)]*(T::mod()/(i+1));f[i+1]=df[i]*inv[i+1];}return f;}template<typename T>vector<T> fps_pow_sparse(const vector<T>&a,const vector<T>&b,ll k,ll l,int deg=-1){int n=a.size(),m=b.size();if(deg==-1)deg=n;assert(a[0]==1);vector<pair<int,T>>c,d;rep(i,n)if(a[i]!=0)c.emplace_back(i,a[i]);rep(i,m)if(b[i]!=0)d.emplace_back(i,b[i]);vector<T>f(deg,0),g(deg,0);for(auto [i,x]:c){for(auto [j,y]:d){if(i+j>=deg+1)continue;T z=x*y;if(i+j<deg)f[i+j]+=z;if(0<i+j&&i+j<=deg)g[i+j-1]-=z*(T(i)*k+T(j)*l);}}return fps_fode_sparse(f,g);}template<typename T>T bostan_mori(vector<T> p,vector<T> q,ll k){int z=1;int n=p.size(),m=q.size();while(z<m*2)z*=2;vector<T>mq(z);p.resize(z,0),q.resize(z,0),mq.resize(z,0);n=m-1;while(k){rep(i,z)mq[i]=q[i]*(i&1?-1:1);dft(p),dft(q),dft(mq);rep(i,z)p[i]*=mq[i];rep(i,z)q[i]*=mq[i];idft(p),idft(q);T inv=T::raw(z).inv();rep(i,z)p[i]*=inv;rep(i,z)q[i]*=inv;vector<T>u(n),v(m);if(k&1)rep(i,n)u[i]=p[i*2+1];else rep(i,n)u[i]=p[i*2];rep(i,m)v[i]=q[i*2];u.resize(z,0),v.resize(z,0);swap(p,u),swap(q,v);k>>=1;}return p[0];}template<typename T>vector<T> berlekamp_massey(const vector<T>&s){const int n=s.size();vector<T>b,c;b.reserve(n+1),c.reserve(n+1);b.emplace_back(1),c.emplace_back(1);T y=1;reps(i,1,n+1){int l=c.size(),m=b.size();T x=0;rep(j,l)x+=c[j]*s[i-l+j];b.emplace_back(0);++m;if(x==0)continue;T f=x/y;if(l<m){auto c2=c;c.insert(c.begin(),m-l,0);rep(j,m)c[m-1-j]-=f*b[m-1-j];b=c2;y=x;}else{rep(j,m)c[l-1-j]-=f*b[m-1-j];}}reverse(all(c));return c;}template<typename T>T kth_term(vector<T>p,ll k){vector<T>q=berlekamp_massey(p);if(T::mod()==998244353){p=ntt_convolution(p,q);p.resize(q.size()-1);return bostan_mori(p,q,k);}auto convolution_naive=[](vector<T>&x,const vector<T>&y)->void {vector<T>temp(x.size()+y.size()-1,0);rep(i,x.size())rep(j,y.size())temp[i+j]+=x[i]*y[j];swap(x,temp);};convolution_naive(p,q);int n=q.size();p.resize(n-1);vector<T>mq(n);while(k){rep(i,n)mq[i]=q[i]*(i&1?-1:1);convolution_naive(p,mq);convolution_naive(q,mq);vector<T>u(n-1),v(n);if(k&1)rep(i,n-1)u[i]=p[i*2+1];else rep(i,n-1)u[i]=p[i*2];rep(i,n)v[i]=q[i*2];swap(p,u),swap(q,v);k>>=1;}if(p.empty())return 0;else return p[0];}using mint=modint1000000007;void SOLVE(){int n;cin>>n;vector<mint>sum(100,0);vector<vector<mint>>dp(100,vector<mint>(3,0));dp[0][0]=1;rep(i,99){rep(j,3){dp[i+1][j]+=dp[i][j]/3;if(i!=98)rep(k,3)if(j!=k)dp[i+2][k]+=dp[i][j]/3;}sum[i+1]=dp[i+1][0];}cout<<kth_term(sum,n).val()<<endl;}