#907719 (C++14) No.2442 線形写像

提出ソース
結果

問題	No.2442 線形写像
ユーザー	umimel
提出日時	2023-08-25 21:45:09
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	5,822 bytes
コンパイル時間	1,840 ms
コンパイル使用メモリ	170,932 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-12-24 08:24:23
合計ジャッジ時間	2,379 ms
ジャッジサーバーID （参考情報）	judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 12 WA * 10
権限があれば一括ダウンロードができます
ソースコード

raw source code
プレゼンテーションモードにする

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i)
#define rep(i, n) drep(i, 0, n - 1)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define fi first
#define se second
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const ll MOD1000000007 = 1000000007;
const ll MOD998244353 = 998244353;
const ll MOD[3] = {999727999, 1070777777, 1000000007};
const ll LINF = 1LL << 60;
const int IINF = (1 << 30) - 1;
template<typename T> struct Edge{
    int to; T w;
    Edge(int to_, T w_=1){
        to = to_;
        w=w_;
    }
};
template<typename T> using Tree = vector<vector<Edge<T>>>;
template<typename T> using Graph = vector<vector<Edge<T>>>;
/* 容量&重み付きエッジ for Dinic */
template<typename T> struct REdge{
    int to;
    T cap;
    T cost;
    int rev;
    REdge(int to_, T cap_, T cost_=1){
        to = to_;
        cap = cap_;
        cost = cost_;
    }
    
    REdge(int to_, T cap_, T cost_, int rev_){
        to = to_;
        cap = cap_;
        cost = cost_;
        rev = rev_;
    }
};
/* 残余グラフ for Dinic */
template<typename T> using RGraph = vector<vector<REdge<T>>>;
template<typename T>
struct mat{
    vector<vector<T>> m; //行列m
    int nrow, ncol;
    
    //コンストラクタ : 第1引数⇒行数, 第2引数⇒列数, 第3引数⇒初期値
    mat():m(vector<vector<T>>()){}
    mat(int h, int w):m(vector<vector<T>>(h, vector<T>(w))){nrow=(int)m.size(); ncol=(int)m[0].size();}
    mat(int h, int w, T d):m(vector<vector<T>>(h, vector<T>(w, d))){nrow=(int)m.size(); ncol=(int)m[0].size();}
    //添え字演算
    vector<T> operator[](const int i) const {return m[i];} //読み取り
    vector<T>& operator[](const int i){return m[i];} //書き込み
    //行列&行列 演算
    mat& operator=(const mat& a){return *a;}
    mat& operator+=(const mat& a){assert(ncol == a.ncol && nrow == a.nrow);rep(i,nrow)rep(j,ncol)m[i][j] += a[i][j]; return *this;}
    mat& operator-=(const mat& a){assert(ncol == a.ncol && nrow == a.nrow);rep(i,nrow)rep(j,ncol)m[i][j] -= a[i][j]; return *this;} 
    mat& operator*=(const mat& a){assert(ncol == a.nrow);mat<T> m2(nrow, a.ncol, 0);rep(i,nrow)rep(j,a.ncol)rep(k,ncol)m2[i][j] += m[i][k]*a[k][j]
        ;ncol = a.ncol;rep(i,nrow)m[i].resize(ncol);rep(i,nrow)rep(j,ncol)m[i][j] = m2[i][j]; return *this;}
    mat operator+(const mat& a) const { return mat(*this) += a;}
    mat operator-(const mat& a) const { return mat(*this) -= a;}
    mat operator*(const mat& a) const { return mat(*this) *= a;}
    bool operator==(const mat& a){assert(ncol == a.ncol && nrow == a.nrow);bool flg = true;rep(i,nrow)rep(j,ncol)if(m[i][j] != a[i][j])flg = false; 
        return flg;}
    //行列&スカラ 演算
    mat& operator+=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] += a;return *this;}
    mat& operator-=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] -= a;return *this;}
    mat& operator*=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] *= a;return *this;}
    mat& operator/=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] /= a;return *this;}
    mat operator+(const T& a) const { return mat(*this) += a;}
    mat operator-(const T& a) const { return mat(*this) -= a;}
    mat operator*(const T& a) const { return mat(*this) *= a;}
    mat operator/(const T& a) const { return mat(*this) /= a;}
    // 回転（degの数だけ時計回りに90度回転）
    mat& rot(int deg){
        mat<T> m2(ncol, nrow);
        if(deg == 1 || deg == 3){
            if(deg == 1)rep(i,nrow)rep(j,ncol)m2[j][nrow -i -1] = m[i][j];
            if(deg == 3)rep(i,nrow)rep(j,ncol)m2[ncol -j -1][i] = m[i][j];
            swap(ncol,nrow); // 列数と行数を入れ替える
            m.resize(nrow);rep(i,nrow)m[i].resize(ncol); //リサイズ
        }
        if(deg == 2)rep(i,nrow)rep(j,ncol)m2[nrow -i -1][ncol -j -1] = m[i][j];
        rep(i,nrow)rep(j,ncol)m[i][j] = m2[i][j];
        return *this;
    }
    // 行列式
    T det(){
        mat<T> sm(*this);
        assert(ncol==nrow);
        T ret = 1;
        for(int i=0; i<nrow; i++){
            int idx = -1;
            for(int j=i; j<nrow; j++){
                if(sm[j][i]!=0) idx=j;
            }
            if(idx==-1) return 0;
            if(i!=idx){
                ret *= -1;
                swap(sm[i], sm[idx]);
            }
            ret*=sm[i][i];
            T vv = sm[i][i];
            for(int j=0; j<nrow; j++){
                sm[i][j] /= vv;
            }
            for(int j=i+1; j<nrow; j++){
                T a = sm[j][i];
                for(int k=0; k<nrow; k++){
                    sm[j][k]-=sm[i][k]*a;
                }
            }
        }
        return ret;
    }
    mat<T> pow(long long t){
        mat<T> ret(nrow, ncol);
        mat<T> sm(nrow, ncol);
        for(int i=0; i<ncol; i++) ret[i][i] = 1;
        for(int i=0; i<nrow; i++)for(int j=0; j<ncol; j++) sm[i][j] = m[i][j];
        while(t > 0){
            if(t & 1) ret *= sm;
            sm *= sm;
            t >>= 1LL;
        }
        return ret;
    }
    // 標準出力
    void show(){
        rep(i,nrow)rep(j,ncol){
            if(j != 0)cout << " ";
            cout << m[i][j];
            if(j==ncol-1)cout << endl;
        }
        return ;
    }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    ll n; cin >> n;
    vector<ll> a((1LL<<n)); rep(i, (1LL<<n)) cin >> a[i];
    if(a[0]!=0){
        cout << "No" << endl;
        return 0;
    }
    for(ll k=1; k<n; k++){
        ll s = (1LL<<k);
        for(ll i=(1LL<<k); i<(1LL<<(k+1)); i++){
            if(a[i]!=a[s]^a[i^s]){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
yukicoder

結果

ソースコード
