結果
問題 | No.2067 ±2^k operations |
ユーザー |
![]() |
提出日時 | 2022-09-02 22:40:34 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,554 bytes |
コンパイル時間 | 15,536 ms |
コンパイル使用メモリ | 317,596 KB |
最終ジャッジ日時 | 2025-02-07 01:37:55 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 8 TLE * 15 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 2000000000000000001 long long dp[2][30][30],ndp[2][30][30]; int main(){ int _t; cin>>_t; rep(_,_t){ long long N; cin>>N; //N = 1LL << 50; //vector dp(2,vector(30,vector<long long>(30,0))); rep(j,2){ rep(k,30){ rep(l,30){ dp[j][k][l] = 0; } } } dp[0][0][2] = 1; bool f = false; for(int i=59;i>=0;i--){ if((N>>i)&1){ f = true; } else if(!f)continue; rep(j,2){ rep(k,30){ rep(l,30){ ndp[j][k][l] = 0; } } } //vector ndp(2,vector(30,vector<long long>(30,0))); rep(j,2){ rep(k,30){ rep(l,30){ if(dp[j][k][l]==0)continue; rep(m,2){ int nj = j,nk = 29,nl = 29; if(j==0 && ((N>>i)&1)==0 && m==1)continue; if(((N>>i)&1) && m==0)nj = 1; if(m==0){ nk = min(nk,k); nl = min(nl,l+1); nk = min(nk,l); } else{ nk = min(nk,k+1); nl = min(nl,l); nl = min(nl,k+2); } ndp[nj][nk][nl] += dp[j][k][l]; } } } } swap(dp,ndp); } long long ans = 0; rep(i,2){ rep(j,30){ rep(k,30){ //if(dp[i][j][k])cout<<i<<','<<j<<','<<k<<endl; ans += dp[i][j][k] * (long long) min(j,k); } } } cout<<ans<<endl; } return 0; }