結果
問題 | No.492 IOI数列 |
ユーザー |
![]() |
提出日時 | 2017-03-10 22:56:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 2,171 bytes |
コンパイル時間 | 1,705 ms |
コンパイル使用メモリ | 170,524 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-24 08:30:16 |
合計ジャッジ時間 | 2,503 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long LL; #define CIN_ONLY if(1) struct cww{cww(){ CIN_ONLY{ ios::sync_with_stdio(false);cin.tie(0); } }}star; #define fin "\n" #define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() #define fi first #define se second #define pb push_back #define DEBUG if(0) #define REC(ret, ...) std::function<ret (__VA_ARGS__)> template <typename T>inline void chmin(T &l,T r){l=min(l,r);} template <typename T>inline void chmax(T &l,T r){l=max(l,r);} template <typename T> istream& operator>>(istream &is,vector<T> &v){ for(auto &it:v)is>>it; return is; } typedef long long LL; typedef LL D; #define S 3 int sz=S; struct M{ D v[S][S]; }mat[64]; const LL mod=1e9+7; void mat_mul(M &a,M& b,M &c){ for(int i=0;i<sz;i++)for(int j=0;j<sz;j++)c.v[i][j]=0; D sum[4],tmp; for(int k=0;k<sz;k++){ for(int i=0;i<sz;i+=4){ sum[0]=a.v[i][k]; sum[1]=a.v[i+1][k]; sum[2]=a.v[i+2][k]; sum[3]=a.v[i+3][k]; for(int j=0;j<sz;j++){ tmp=b.v[k][j]; (c.v[i][j]+=sum[0]*tmp)%=mod; (c.v[i+1][j]+=sum[1]*tmp)%=mod; (c.v[i+2][j]+=sum[2]*tmp)%=mod; (c.v[i+3][j]+=sum[3]*tmp)%=mod; } } } } int main(){ LL N; cin>>N; mat[0].v[0][0]=100; mat[0].v[0][1]=0; mat[0].v[0][2]=1; mat[0].v[1][0]=1; mat[0].v[1][1]=0; mat[0].v[1][2]=0; mat[0].v[2][0]=0; mat[0].v[2][1]=0; mat[0].v[2][2]=1; REP(i,63)mat_mul(mat[i],mat[i],mat[i+1]); vector<LL> res{1,0,1}; LL M=N-1; for(int b=0;M;M>>=1,b++){ if(M&1){ vector<LL> nxt(3,0); REP(i,3)REP(j,3)(nxt[i]+=res[j]*mat[b].v[i][j])%=mod; swap(res,nxt); } } cout<<res[0]<<endl; if(N<11){ cout<<1; REP(i,N-1)cout<<"01";cout<<endl; } else { M=N%11; if(M==0)cout<<0; else { cout<<1; REP(i,M-1)cout<<"01"; cout<<endl; } } return 0; }