結果

問題 No.183 たのしい排他的論理和(EASY)
コンテスト
ユーザー Niwaka
提出日時 2022-03-23 07:24:26
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,828 bytes
コンパイル時間 4,007 ms
コンパイル使用メモリ 145,008 KB
実行使用メモリ 664,704 KB
最終ジャッジ日時 2024-10-11 04:38:42
合計ジャッジ時間 15,500 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 7 WA * 5 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

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;
}

int main(){ 
    cin >> N;
    vector<llong> A(N);
    map<llong, llong> mp;
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    vector<vector<llong> > dp(N, vector<llong>(16385, -1));
    cout << dfs(0, 0, A, mp, dp) << endl;
}
0