結果

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

ソースコード

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;
LL N;
LL a[100001];//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[1000001];
LL solve2(LL x,LL mod){
   if(x==1)return 1;
   if(x==2)return 101;
   if(x<1000001){
      if(dp[x]!=-1)return dp[x];
   }
   dp[x]=(solve2((x+1)/2,mod)*solve(x/2,mod)+solve2(x/2,mod))%mod;
   //cout<<x<<" "<<(solve2((x+1)/2,mod))<<" "<<solve(x/2,mod)<<" "<<(solve2(x/2,mod))%mod<<" "<<(solve2((x+1)/2,mod)*solve(x/2,mod)+solve2(x/2,mod))<<endl;
   return dp[x];
}
int main(){
        REP(i,1000001){
            dp[i]=-1;
        }
	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