# 某島

… : "…アッカリ～ン . .. . " .. .
August 15, 2022

## Problem C. Matrix Reducing

#include <lastweapon/io>
using namespace lastweapon;
const int N = 10;
int A[N][N], B[N][N];
int h1, w1, h2, w2; VI H;

bool dfs(int k1 = 0, int k2 = 0, int h0 = 0, int w0 = 0) {
if (k1 == h2) {
if (k2 == w2) {
return 1;
} else {
FOR(w, w0, w1-(w2-1)+k2) {
bool ok = 1;
REP(i, h2) if (A[H[i]][w] != B[i][k2]) {
ok = 0;
break;
}
if (!ok) continue;
if (dfs(k1, k2+1, h0, w0+1)) return 1;
}
}
} else {
FOR(h, h0, h1-(h2-1)+k1) {
H.push_back(h);
if (dfs(k1+1, k2, h0+1, w0)) return 1;
H.pop_back();
}
}
return 0;
}

int main(){
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
RD(h1, w1); REP(i, h1) REP(j, w1) RD(A[i][j]);
RD(h2, w2); REP(i, h2) REP(j, w2) RD(B[i][j]);
puts(dfs() ? "Yes" : "No");
}



## Problem E. Blackout 2

#include <lastweapon/io>
#include <lastweapon/dsu>
using namespace lastweapon;
const int N = int(5e5) + 9;

int n, m, en, qn;
struct edge {
int a, b; bool ok;
void in() {
RD(a, b); ok = 1;
if (a > n) a = 0;
if (b > n) b = 0;
}
} E[N];
int Q[N], Z[N];

int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif

RD(n, m, en); REP(i, en) E[i].in();
RD(qn); REP(i, qn) E[--RD(Q[i])].ok = 0;
dsu d(n+1); REP(i, en) if (E[i].ok) d.merge(E[i].a, E[i].b);

DWN(i, qn, 0) {
Z[i] = d.size(0);
d.merge(E[Q[i]].a, E[Q[i]].b);
}

REP(i, qn) printf("%d\n", Z[i]-1);
}



atl 的 dsu 居然還帶 size 函數。。。

## Problem Ex. Perfect Binary Tree

#include <lastweapon/number>
using namespace lastweapon;
const int N = int(3e5) + 9, LOGN = 20;
VI adj[N]; Int f[N][LOGN], s[N][LOGN]; int p[N], d[N];
int n;

void upd(int x) {
int y = p[x]; d[x] = d[y] + 1; if (d[x] >= LOGN) return;
Int d = f[x][0] = 1; for (int i=0;x;++i) {
s[y][i] += d; d *= (s[y][i] - f[x][i]); f[y][i+1] += d;
x = y; y = p[x];
}
}

int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
MOD = 998244353;
RD(n); cout << (f[0][0] = 1) << endl;
FOR(i, 1, n) {