結果

問題 No.420 mod2漸化式
コンテスト
ユーザー beet
提出日時 2018-07-30 13:44:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 1,709 bytes
コンパイル時間 1,777 ms
コンパイル使用メモリ 177,796 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-13 19:27:24
合計ジャッジ時間 2,903 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
Int next_combination(Int sub) {
  Int x = sub & -sub, y = sub + x;
  return (((sub & ~y) / x) >> 1) | y;
}
void calc(){
  const Int n=31;
  for(Int k=1;k<=n;k++){
    Int cnt=0,ans=0;
    for(Int bit=(1LL<<k)-1;bit<(1LL<<n);bit=next_combination(bit)) cnt++,ans+=bit;  
    cout<<"dp["<<k<<"]=P("<<cnt<<","<<ans<<");"<<endl;
  }
}
signed main(){
  using P = pair<Int, Int>;
  map<Int, P> dp;
  dp[0]=P(1,0);
  dp[1]=P(31,2147483647);
  dp[2]=P(465,64424509410);
  dp[3]=P(4495,934155386445);
  dp[4]=P(31465,8718783606820);
  dp[5]=P(169911,58851789346035);
  dp[6]=P(736281,306029304599382);
  dp[7]=P(2629575,1275122102497425);
  dp[8]=P(7888725,4371847208562600);
  dp[9]=P(20160075,12569060724617475);
  dp[10]=P(44352165,30724370660176050);
  dp[11]=P(84672315,64521178386369705);
  dp[12]=P(141120525,117311233429763100);
  dp[13]=P(206253075,185742786263791575);
  dp[14]=P(265182525,257182319442172950);
  dp[15]=P(300540195,312292816465495725);
  dp[16]=P(300540195,333112337563195440);
  dp[17]=P(265182525,312292816465495725);
  dp[18]=P(206253075,257182319442172950);
  dp[19]=P(141120525,185742786263791575);
  dp[20]=P(84672315,117311233429763100);
  dp[21]=P(44352165,64521178386369705);
  dp[22]=P(20160075,30724370660176050);
  dp[23]=P(7888725,12569060724617475);
  dp[24]=P(2629575,4371847208562600);
  dp[25]=P(736281,1275122102497425);
  dp[26]=P(169911,306029304599382);
  dp[27]=P(31465,58851789346035);
  dp[28]=P(4495,8718783606820);
  dp[29]=P(465,934155386445);
  dp[30]=P(31,64424509410);
  dp[31]=P(1,2147483647);
  Int x;
  cin>>x;
  cout<<dp[x].first<<" "<<dp[x].second<<endl;
  return 0;
}
0