結果

問題 No.2853 A + B Problem
ユーザー HIcoderHIcoder
提出日時 2024-08-26 22:52:43
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,747 bytes
コンパイル時間 1,354 ms
コンパイル使用メモリ 119,252 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-08-26 22:52:46
合計ジャッジ時間 2,638 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 WA -
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
6,944 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<cassert>
#include<random>
#include<set>
#include<map>
#include<cassert>
#include<unordered_map>
#include<bitset>
#include<numeric>
#include<algorithm>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int inf=1<<30;
const ll INF=1LL<<62;
using P = pair<int,int>;
typedef pair<int,P> PP; 
const ll MOD=998244353;
const int MAXN=100000;

ull dp[65][2][2];

int main(){
    ll N;
    cin>>N;
    
    dp[0][1][1]=1;
    
    for(int i=0;i<63;i++){//AとBのi桁目までを決めたときの場合の数
        int c=62-i;
        for(int t=0;t<2;t++){//
            for(int f=0;f<2;f++){

               
                
                for(int j=0;j<2;j++){
                    for(int k=0;k<2;k++){
                        int x=j^k;//Aのc桁目がj,Bのc桁目がk
                        int u=(N>>c)&1;
                        bool ng=false;

                        if(x!=u) ng=true;

                        int to_t=t,to_f=f;
                        if(t==1){
                            if((N>>c)&1){
                                if(j==1){
                                    to_t=1;
                                }else{
                                    //j==0
                                    to_t=0;
                                }
                            }else{
                                //((N>>c)&1)==0
                                if(j==1){
                                    ng=true;
                                }else{
                                    to_t=1;
                                }
                            }
                        }

                        if(f==1){
                            if((N>>c)&1){
                                if(k==1){
                                    to_f=1;
                                }else{
                                    //k==0
                                    to_f=0;
                                }
                            }else{
                                //(N>>c)&1==0
                                if(k==1){
                                    ng=true;
                                }else{
                                    to_f=1;
                                }
                            }
                        }

                        if(ng) continue;
                        
                        dp[i+1][to_t][to_f]+=dp[i][t][f];

                    }
                }

            }
        }
    }

    ull ans=0;
    for(int t=0;t<2;t++){
        for(int f=0;f<2;f++){
            ans+=dp[63][t][f];
        }
    }
    ans-=2;//(0,N),(N,0)を除く
    cout<<ans<<endl;

}
0