結果

問題 No.492 IOI数列
ユーザー rapurasurapurasu
提出日時 2017-03-11 00:56:43
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,432 bytes
コンパイル時間 1,319 ms
コンパイル使用メモリ 144,972 KB
実行使用メモリ 16,004 KB
最終ジャッジ日時 2023-09-06 14:58:37
合計ジャッジ時間 3,753 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
16,004 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます

ソースコード

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