結果

問題 No.492 IOI数列
コンテスト
ユーザー rapurasu
提出日時 2017-03-11 00:56:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,432 bytes
コンパイル時間 1,741 ms
コンパイル使用メモリ 159,572 KB
実行使用メモリ 19,740 KB
最終ジャッジ日時 2024-06-24 09:24:01
合計ジャッジ時間 4,142 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
#define dp_size 1000001
LL N;
LL a[1000001];//100^x
LL solve(LL x,LL mod){//x^100を求める
   //cout<<x<<"aa"<<endl;
   a[0]=100;
   //a[1]=100;
   for(int i=1;i<100;i++){
       a[i]=(a[i-1]*a[i-1])%mod;
   }
   LL ans=1;
   LL count=0;
   while(x>0){
      if(x%2==1){
         ans=(ans*a[count])%mod;
      }
      count++;
      x/=2;
   }
   //cout<<ans<<"bbb"<<endl;;
   return ans;
}
LL dp[dp_size];
LL solve2(LL x,LL mod){
   if(x==1)return 1;
   if(x==2)return 101;
   //cout<<"a"<<endl;
   if(x<dp_size){
      //cout<<x<<"b"<<dp[x]<<endl;
      if(dp[x]!=-1)return dp[x];
   }
   LL temp;
  // cout<<"c"<<endl;
   temp=solve2((x+1)/2,mod);
  // cout<<"d"<<endl;
   temp*=solve(x/2,mod);
  // cout<<"e"<<endl;
   temp+=solve2(x/2,mod);
   temp%=mod;
  // cout<<"f"<<endl;
   if(x<1000001){
      dp[x]=temp;
   }
   return temp;
}
int main(){
        memset(dp,-1,sizeof(dp));
	LL N;
	cin>>N;
	/*REP(i,9){
	    cout<<solve2(6,10000000000000007)<<endl;
	}*/
        cout<<solve2(N,1000000007)<<endl;
        if(N%11==0){
           cout<<0<<endl;
           return 0;
        }
        REP(i,N%11-1){
            cout<<"10";
        }
        cout<<"1"<<endl;
	return(0);
}
0