結果
| 問題 |
No.2293 無向辺 2-SAT
|
| コンテスト | |
| ユーザー |
 Daylight
|
| 提出日時 | 2023-05-06 11:03:06 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 405 ms / 4,000 ms |
| コード長 | 16,091 bytes |
| コンパイル時間 | 4,747 ms |
| コンパイル使用メモリ | 237,456 KB |
| 実行使用メモリ | 37,560 KB |
| 最終ジャッジ日時 | 2024-06-22 17:51:53 |
| 合計ジャッジ時間 | 32,170 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 53 |
ソースコード
public import std;
DList!string scan_buffer;
DList!char char_buffer;
static this() {
scan_buffer = DList!(string)();
char_buffer = DList!(char)();
}
void cin()() {
}
void cin(T, A...)(ref T a, ref A tail) {
import std.traits : isArray;
static if (typeof(a).stringof == "string") {
if (!char_buffer.empty) {
a = char_buffer.array.map!(x => x.to!string).join();
char_buffer.clear();
} else {
while (scan_buffer.empty) {
foreach (t; readln.split) {
if (t.length == 0) {
continue;
}
scan_buffer.insert(t);
}
}
auto token = scan_buffer.front;
scan_buffer.removeFront();
a = token;
}
} else static if (typeof(a).stringof == "char") {
if (!char_buffer.empty) {
a = char_buffer.front();
char_buffer.removeFront();
} else {
while (scan_buffer.empty) {
foreach (t; readln.split) {
if (t.length == 0) {
continue;
}
scan_buffer.insert(t);
}
}
auto token = scan_buffer.front;
scan_buffer.removeFront();
a = token[0];
if (token.length > 1) {
foreach (c; token[1 .. $]) {
char_buffer.insertBack(c);
}
}
}
} else static if (typeof(a).stringof == "char[]") {
if (a.length == 0) {
string token;
cin(token);
foreach (c; token) {
a ~= c;
}
} else {
foreach (ref v; a) {
cin(v);
}
}
} else static if (isArray!(typeof(a))) {
foreach (ref v; a) {
cin(v);
}
} else static if (isTuple!(typeof(a))) {
foreach (i, _; a) {
cin(a[i]);
}
} else {
if (!char_buffer.empty) {
writeln(char_buffer.array.map!(x => x.to!string));
a = char_buffer.array.map!(x => x.to!string).join().to!T;
char_buffer.clear();
} else {
while (scan_buffer.empty) {
foreach (t; readln.split) {
if (t.length == 0) {
continue;
}
scan_buffer.insert(t);
}
}
auto token = scan_buffer.front;
scan_buffer.removeFront();
a = token.to!T;
}
}
cin(tail);
}
bool chmin(T)(ref T a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
bool chmax(T)(ref T a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
alias PQueue(T = long, alias less = "a<b") = BinaryHeap!(Array!T, less);
class RollbackUnionFind {
import std;
private:
int N;
int[] p;
alias P = Tuple!(int, int);
DList!P history;
public:
this(int size) {
N = size;
p = new int[](size);
p.fill(-1);
}
bool same(int x, int y) {
return leader(x) == leader(y);
}
void merge(int x, int y) {
link(leader(x), leader(y));
}
void link(int x, int y) {
if (x == y)
return;
if (p[x] > p[y])
swap(x, y);
if (p[x] == p[y]) {
history.insertBack(P(x, p[x]));
p[x]--;
}
history.insertBack(P(y, p[y]));
p[y] = x;
}
int leader(int x) {
if (p[x] < 0)
return x;
else
return leader(p[x]);
}
void snapshot() {
history.clear();
}
void rollback() {
while (!history.empty()) {
auto pa = history.back();
history.removeBack();
p[pa[0]] = pa[1];
}
}
}
import std.typecons : Tuple;
ulong safeMod(long x, long m) @safe pure nothrow @nogc
{
x %= m;
if (x < 0)
x += m;
return x;
}
ulong[2] umul128(ulong a, ulong b) @safe @nogc pure nothrow
{
immutable ulong au = a >> 32;
immutable ulong bu = b >> 32;
immutable ulong al = a & ((1UL << 32) - 1);
immutable ulong bl = b & ((1UL << 32) - 1);
ulong t = al * bl;
immutable ulong w3 = t & ((1UL << 32) - 1);
ulong k = t >> 32;
t = au * bl + k;
k = t & ((1UL << 32) - 1);
immutable ulong w1 = t >> 32;
t = al * bu + k;
k = t >> 32;
return [au * bu + w1 + k, t << 32 + w3];
}
struct Barrett
{
uint _m;
ulong im;
this(uint m) @safe @nogc pure nothrow
{
_m = m;
im = (cast(ulong)(-1)) / m + 1;
}
uint umod() @safe @nogc pure nothrow
{
return _m;
}
uint mul(uint a, uint b) @safe @nogc pure nothrow
{
ulong z = a;
z *= b;
immutable ulong x = umul128(z, im)[0];
uint v = cast(uint)(z - x * _m);
if (_m <= v)
v += _m;
return v;
}
}
long ctPowMod(long x, long n, int m) @safe pure nothrow @nogc
{
if (m == 1)
return 0;
uint _m = cast(uint) m;
ulong r = 1;
ulong y = safeMod(x, m);
while (n)
{
if (n & 1)
r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
bool ctIsPrime(int n) @safe pure nothrow @nogc
{
if (n <= 1)
return false;
if (n == 2 || n == 7 || n == 61)
return true;
if (n % 2 == 0)
return false;
long d = n - 1;
while (d % 2 == 0)
d /= 2;
foreach (a; [2, 7, 61])
{
long t = d;
long y = ctPowMod(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1)
{
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0)
{
return false;
}
}
return true;
}
enum bool isPrime(int n) = ctIsPrime(n);
Tuple!(long, long) invGcd(long a, long b) @safe pure nothrow @nogc
{
a = safeMod(a, b);
if (a == 0)
return Tuple!(long, long)(b, 0);
long s = b, t = a, m0 = 0, m1 = 1;
while (t)
{
immutable long u = s / t;
s -= t * u;
m0 -= m1 * u;
long tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0)
m0 += b / s;
return Tuple!(long, long)(s, m0);
}
int ctPrimitiveRoot(int m) @safe pure nothrow @nogc
{
if (m == 2)
return 1;
if (m == 167_772_161)
return 3;
if (m == 469_762_049)
return 3;
if (m == 754_974_721)
return 11;
if (m == 998_244_353)
return 3;
int[20] divs;
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0)
x /= 2;
for (int i = 3; (cast(long) i) * i <= x; i += 2)
if (x % i == 0)
{
divs[cnt++] = i;
while (x % i == 0)
x /= i;
}
if (x > 1)
divs[cnt++] = x;
for (int g = 2;; g++)
{
bool ok = true;
foreach (i; 0 .. cnt)
if (ctPowMod(g, (m - 1) / divs[i], m) == 1)
{
ok = false;
break;
}
if (ok)
return g;
}
}
enum primitiveRoot(int m) = ctPrimitiveRoot(m);
struct StaticModInt(int m) if (1 <= m) {
import std.traits : isSigned, isUnsigned, isSomeChar;
alias mint = StaticModInt;
public:
static int mod() {
return m;
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
this(T)(T v) if (isSigned!T) {
long x = cast(long)(v % cast(long)(umod()));
if (x < 0)
x += umod();
_v = cast(uint)(x);
}
this(T)(T v) if (isUnsigned!T || isSomeChar!T) {
_v = cast(uint)(v % umod());
}
this(bool v) {
_v = cast(uint)(v) % umod();
}
auto opAssign(T)(T v)
if (isSigned!T || isUnsigned!T || isSomeChar!T || is(T == bool)) {
return this = mint(v);
}
inout uint val() pure {
return _v;
}
ref mint opUnary(string op)() pure nothrow @safe if (op == "++") {
_v++;
if (_v == umod())
_v = 0;
return this;
}
ref mint opUnary(string op)() pure nothrow @safe if (op == "--") {
if (_v == 0)
_v = umod();
_v--;
return this;
}
mint opUnary(string op)() if (op == "+" || op == "-") {
mint x;
return mixin("x " ~ op ~ " this");
}
ref mint opOpAssign(string op, T)(T value) if (!is(T == mint)) {
mint y = value;
return opOpAssign!(op)(y);
}
ref mint opOpAssign(string op, T)(T value) if (op == "+" && is(T == mint)) {
_v += value._v;
if (_v >= umod())
_v -= umod();
return this;
}
ref mint opOpAssign(string op, T)(T value) if (op == "-" && is(T == mint)) {
_v -= value._v;
if (_v >= umod())
_v += umod();
return this;
}
ref mint opOpAssign(string op, T)(T value) if (op == "*" && is(T == mint)) {
ulong z = _v;
z *= value._v;
_v = cast(uint)(z % umod());
return this;
}
ref mint opOpAssign(string op, T)(T value) if (op == "/" && is(T == mint)) {
return this = this * value.inv();
}
ref mint opOpAssign(string op, T)(T value)
if (op == "^^" && (is(T == int) || is(T == long))) {
return this = this.pow(value);
}
mint pow(long n) const pure {
assert(0 <= n);
mint x = this, r = 1;
while (n) {
if (n & 1)
r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const pure {
static if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = invGcd(_v, mod());
assert(eg[0] == 1);
return mint(eg[1]);
}
}
mint opBinary(string op, R)(const R value) const pure
if (op == "+" || op == "-" || op == "*" || op == "/") {
static if (is(R == mint)) {
mint x;
x += this;
return x.opOpAssign!(op)(value);
} else {
mint x;
x += this;
mint y = value;
return x.opOpAssign!(op)(y);
}
}
mint opBinary(string op, R)(const R value) const pure
if (op == "^^") {
return pow(value);
}
mint opBinaryRight(string op, L)(const L value) const if (!is(L == mint)) {
mint y = value;
return y.opBinary!(op)(this);
}
bool opEquals(R)(const R value) const {
static if (is(R == mint)) {
return _v == value._v;
} else {
mint y = mint(value);
return this == y;
}
}
private:
uint _v;
uint umod() pure const {
return m;
}
enum bool prime = isPrime!(m);
}
struct DynamicModInt(int id) {
import std.traits : isSigned, isUnsigned, isSomeChar;
alias mint = DynamicModInt;
public:
static int mod() {
return bt.umod();
}
static void setMod(int m) {
assert(1 <= m);
bt = Barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
this(T)(T v) if (isSigned!T) {
long x = cast(long)(v % cast(long)(umod()));
if (x < 0)
x += umod();
_v = cast(uint)(x);
}
this(T)(T v) if (isUnsigned!T || isSomeChar!T) {
_v = cast(uint)(v % umod());
}
this(bool v) {
_v = cast(uint)(v) % umod();
}
auto opAssign(T)(T v)
if (isSigned!T || isUnsigned!T || isSomeChar!T || is(T == bool)) {
return this = mint(v);
}
inout uint val() {
return _v;
}
ref mint opUnary(string op)() nothrow @safe if (op == "++") {
_v++;
if (_v == umod())
_v = 0;
return this;
}
ref mint opUnary(string op)() nothrow @safe if (op == "--") {
if (_v == 0)
_v = umod();
_v--;
return this;
}
mint opUnary(string op)() if (op == "+" || op == "-") {
mint x;
return mixin("x " ~ op ~ " this");
}
ref mint opOpAssign(string op, T)(T value) if (!is(T == mint)) {
mint y = value;
return opOpAssign!(op)(y);
}
ref mint opOpAssign(string op, T)(T value) if (op == "+" && is(T == mint)) {
_v += value._v;
if (_v >= umod())
_v -= umod();
return this;
}
ref mint opOpAssign(string op, T)(T value) if (op == "-" && is(T == mint)) {
_v -= value._v;
if (_v >= umod())
_v += umod();
return this;
}
ref mint opOpAssign(string op, T)(T value) if (op == "*" && is(T == mint)) {
_v = bt.mul(_v, value._v);
return this;
}
ref mint opOpAssign(string op, T)(T value) if (op == "/" && is(T == mint)) {
return this = this * value.inv();
}
ref mint opOpAssign(string op, T)(T value)
if (op == "^^" && (is(T == int) || is(T == long))) {
return this = this.pow(value);
}
mint pow(long n) const {
assert(0 <= n);
mint x = this, r = 1;
while (n) {
if (n & 1)
r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = invGcd(_v, mod());
assert(eg[0] == 1);
return mint(eg[1]);
}
mint opBinary(string op, R)(const R value)
if (op == "+" || op == "-" || op == "*" || op == "/") {
static if (is(R == mint)) {
mint x;
x += this;
return x.opOpAssign!(op)(value);
} else {
mint y = value;
return opOpAssign!(op)(y);
}
}
mint opBinary(string op, R)(const R value) const
if (op == "^^") {
return pow(value);
}
mint opBinaryRight(string op, L)(const L value) const if (!is(L == mint)) {
mint y = value;
return y.opBinary!(op)(this);
}
bool opEquals(R)(const R value) const {
static if (is(R == mint)) {
return _v == value._v;
} else {
mint y = mint(value);
return this == y;
}
}
private:
uint _v;
static Barrett bt = Barrett(998_244_353);
uint umod() {
return bt.umod();
}
}
alias modint998244353 = StaticModInt!(998244353);
alias modint1000000007 = StaticModInt!(1000000007);
alias modint = DynamicModInt!(-1);
alias mint = modint998244353;
void main() {
int N, Q;
cin(N, Q);
auto dsu = new RollbackUnionFind(N * 2);
int cnt = N;
bool zero = false;
foreach (q; 0 .. Q) {
int k;
cin(k);
if (k == 1) {
int u, v;
cin(u, v);
u--;
v--;
if (!dsu.same(u, v)) {
dsu.merge(u, v);
dsu.merge(u + N, v + N);
cnt--;
}
if (dsu.same(u, u + N)) {
zero = true;
}
if (zero) {
0.writeln;
} else {
(mint(2) ^^ cnt).val.writeln;
}
} else if (k == 2) {
int u, v;
cin(u, v);
u--;
v--;
if (!dsu.same(u, v + N)) {
dsu.merge(u, v + N);
dsu.merge(u + N, v);
cnt--;
}
if (dsu.same(u, u + N)) {
zero = true;
}
if (zero) {
0.writeln;
} else {
(mint(2) ^^ cnt).val.writeln;
}
} else {
zero = false;
cnt = N;
dsu.rollback();
(mint(2) ^^ cnt).val.writeln;
}
}
}