結果

問題 No.183 たのしい排他的論理和(EASY)
ユーザー NiwakaNiwaka
提出日時 2022-03-23 08:08:00
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,896 bytes
コンパイル時間 3,152 ms
コンパイル使用メモリ 147,152 KB
実行使用メモリ 17,664 KB
最終ジャッジ日時 2024-10-11 05:28:07
合計ジャッジ時間 10,050 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 WA * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <sstream>
#include <set>
#include<stack>
#include <utility>
#include <tuple>
#include <unordered_map>
#include <string.h>
#include <iomanip>
#include <deque>
#include <climits>
#include <list>
#include <bitset>
//const long long MOD = 1000000000+7;
//const long long MOD = 998244353;
const long long MAX = 1000000000000000001;
//const long long MOD = 1000000000000000007;

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;
#define INF (llong)1<<60
#define DEBUG cout << "Hello" << endl;
//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//sort(s.begin(), s.end(), greater<char>())
//size()	文字数を返す
//Insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//c_str()変換
//文字列の比較は、<=や==などを使え
//replace関数を使い、簡単に文字列を置換
//リバース関数：reverse(str.begin(), str.end());
//map<type, type> dict;で宣言
//グラフ理論用変数
//vector<vector<llong> > graph(N);

//ソート
//降順sort(v.begin(), v.end(), std::greater<Type>());

//大文字から小文字へんかん
//w[i] = w[i]-'A'+'a';

//vector
//assignメソッド　引数：サイズ、値
//与えられたサイズと値でvectorを初期化する

//queueクラス
//find()次に取り出す値の表示をする。
//pop()値を取り出す。戻り値はなし
//push()キューに値をプッシュする

//priority_queueクラス

//切り上げ
//ceil
//floor

//size()で返すのは、符号無し整数
//vectorが0の時は、
//for(int k=0; k<(int)temp_list.size()-1; k++)

/***
vector<llong> v;
do{

}while(next_permutation(v.begin(), v.end()));
***/

//二分探索カンニング
/***
llong right, left, middle;
right = 2e9;//2000000000
left  = 0;
while (right-left>1){
    middle = left + (right - left) / 2;
***/

//double型
//小数点以下10桁
//printf("%.10lf\n", ans);


/***
//const llong mod = 1000000007;
//const llong mod = 998244353;
class mint {
    public:
        llong x; // typedef long long llong;
        mint(llong x=0):x((x%mod+mod)%mod){}
        mint operator-() const { return mint(-x);}
        mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
        }
        mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
        }
        mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
        mint operator+(const mint a) const { return mint(*this) += a;}
        mint operator-(const mint a) const { return mint(*this) -= a;}
        mint operator*(const mint a) const { return mint(*this) *= a;}
        mint pow(llong t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
        }

        // for prime mod
        mint inv() const { return pow(mod-2);}
        mint& operator/=(const mint a) { return *this *= a.inv();}
        mint operator/(const mint a) const { return mint(*this) /= a;}
};
***/

/***
llong dfs(llong i, llong n, llong N, vector<vector<llong>>& dp){
    if(i==N){
        return 1;
    }
    if(dp[i][n]!=-1){
        return dp[i][n];
    }
    mint total=0;
    if(n-1>=1)total += dfs(i+1, n-1, N, dp);
    total += dfs(i+1, n, N, dp);
    if(n+1<=9)total += dfs(i+1, n+1, N, dp);
    return dp[i][n]=total.x;
}
***/
//llong dx[4] = { 0, 1, 0, -1 };
//llong dy[4] = { 1, 0, -1, 0 };

llong N;

llong dfs(llong i, llong sum, vector<llong>& A, map<llong, llong>& table, vector<vector<llong> >& dp){
    if(i==N){
        if(table.count(sum)==0){
            table[sum]++;
            return 1;
        }
        return 0;
    }
    if(dp[i][sum]!=-1){
        return dp[i][sum];
    }
    llong ans=0;
    ans = dfs(i+1, sum^A[i], A, table, dp)+dfs(i+1, sum, A, table, dp);
    return dp[i][sum]=ans;
}

//result = x^a
//を満たすxを求める
llong F(llong result, llong a){
    llong ans=0;
    for(int i=0; i<=14; i++){//桁数が14の場合。
        if((result>>i)&1){
            if((a>>i)&1){
                continue;
            }else{
                ans = ans|(1<<i);
            }
        }else{
            if((a>>i)&1){
                ans = ans|(1<<i);
            }else{
                continue;
            }
        }
    }
    return ans;
}

void TestF(){
    llong result;
    llong a;
    llong x;
    if(F(5, 1)!=4){
        cout << "Expected F(5, 1)==4 " << endl;
        return;
    }
    result = 0;
    a      = 3;
    x      = 3;
    if(F(result, a)!=x){
        cout << "Expected F(" << result << "," << a << ")==" << x << endl;
        return;
    }
    cout << "Success!!" << endl;
}

int main(){ 
    cin >> N;
    vector<llong> A(N+1);
    for(int i=1; i<=N; i++){
        cin >> A[i];
    }
    vector<vector<bool> > dp(N+1, vector<bool>(16385, false));
    dp[0][0] = true;
    for(int i=1; i<=N; i++){
        for(int j=0; j<=dp[i].size(); j++){
            dp[i][j] = dp[i-1][j];
            dp[i][j] = dp[i-1][j]|dp[i-1][F(j, A[i])];
        }
    }
    llong ans=0;
    for(int i=0; i<dp[N].size(); i++){
        if(dp[N][i])ans++;
    }
    cout << ans << endl;
}
0