結果

問題 No.2853 A + B Problem
ユーザー HIcoder
提出日時 2024-08-26 22:52:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,747 bytes
コンパイル時間 1,161 ms
コンパイル使用メモリ 113,824 KB
最終ジャッジ日時 2025-02-24 02:21:32
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 20
権限があれば一括ダウンロードができます

ソースコード

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