QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #484240 | #7413. Determinant | duankaidi | WA | 2ms | 12068kb | C++23 | 7.6kb | 2024-07-19 17:01:28 | 2024-07-19 17:01:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template<class T>
T power(T a, i64 b) {
T res = 1;
for (; b; b >>= 1, a *= a) {
if (b & 1)
res *= a;
}
return res;
}
template<const i64 P>
class ModInt {
public:
i64 x;
static i64 Mod;
ModInt() : x{0} {}
ModInt(int _x) : x{(_x % getMod() + getMod()) % getMod()} {}
ModInt(i64 _x) : x{(_x % getMod() + getMod()) % getMod()} {}
static void setMod(i64 Mod_) {
Mod = Mod_;
}
static i64 getMod() {
return !P ? Mod : P;
}
explicit constexpr operator int() const {
return x;
}
ModInt &operator += (ModInt a) & {
x = x + a.x >= getMod() ? x + a.x - getMod() : x + a.x;
return (*this);
}
ModInt &operator -= (ModInt a) & {
x = x - a.x < 0 ? x - a.x + getMod() : x - a.x;
return (*this);
}
ModInt &operator *= (ModInt a) & {
(x *= a.x) %= getMod();
return (*this);
}
constexpr ModInt inv() {
return power((*this), getMod() - 2);
}
ModInt &operator /= (ModInt a) & {
return (*this) *= a.inv();
}
friend ModInt operator + (ModInt lhs, ModInt rhs) {
return lhs += rhs;
}
friend ModInt operator - (ModInt lhs, ModInt rhs) {
return lhs -= rhs;
}
friend ModInt operator * (ModInt lhs, ModInt rhs) {
return lhs *= rhs;
}
friend ModInt operator / (ModInt lhs, ModInt rhs) {
return lhs /= rhs;
}
friend std::istream &operator >> (std::istream &is, ModInt &p) {
return is >> p.x;
}
friend std::ostream &operator << (std::ostream &os, ModInt p) {
return os << p.x;
}
int operator !() {
return !x;
}
friend bool operator == (ModInt lhs, ModInt rhs) {
return lhs.x == rhs.x;
}
friend bool operator != (ModInt lhs, ModInt rhs) {
return lhs.x != rhs.x;
}
ModInt operator -() {
return ModInt(getMod() - x);
}
ModInt &operator ++() & {
++x;
return *this;
}
ModInt operator ++(int) {
ModInt temp = *this;
++*this;
return temp;
}
} ;
template<>
i64 ModInt<0>::Mod = 1E9 + 7;
constexpr int P = 998244353;
using Z = ModInt<P>;
struct Comb {
int n;
vector<Z> _fac;
vector<Z> _invfac;
vector<Z> _inv;
Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
Comb(int n) : Comb() {init(n);}
void init(int m) {
m = min<int>(m, Z::getMod() - 1);
if (m <= n) return;
_fac.resize(m + 1);
_invfac.resize(m + 1);
_inv.resize(m + 1);
for (int i = n + 1; i <= m; i++) _fac[i] = _fac[i - 1] * i;
_invfac[m] = _fac[m].inv();
for (int i = m; i > n; i--) {
_invfac[i - 1] = _invfac[i] * i;
_inv[i] = _invfac[i] * _fac[i - 1];
} n = m;
}
Z fac(int m) {if (m > n) init(2 * m); return _fac[m];}
Z invfac(int m) {if (m > n) init(2 * m); return _invfac[m];}
Z inv(int m) {if (m > n) init(2 * m); return _inv[m];}
Z binom(int n, int m) {return n < m || m < 0 ? 0 : fac(n) * invfac(m) * invfac(n - m);}
} comb;
const int N = 3E4 + 5, M = 5E5 + 5;
int n, m, k;
int head[N], nex[M << 1], to[M << 1], cnt = 1;
bool bridge[M << 1];
int dfn[N], low[N], tot;
vector<int> vec[N];
void ad(int x, int y) {
to[++cnt] = y;
nex[cnt] = head[x];
head[x] = cnt;
}
void add(int x, int y) {ad(x, y); ad(y, x);}
void tarjan(int x, int fr_edge) {
dfn[x] = low[x] = ++tot;
for (int i = head[x]; i; i = nex[i]) {
int v = to[i];
if (!dfn[v]) {
tarjan(v, i);
low[x] = min(low[x], low[v]);
if (low[v] > dfn[x])
bridge[i] = bridge[i ^ 1] = 1;
} else if ((i ^ 1) != fr_edge)
low[x] = min(low[x], dfn[v]);
}
}
int t, dcc[N];
void dfs(int x) {
dcc[x] = t;
for (int i = head[x]; i; i = nex[i]) {
int v = to[i];
// cerr << x << ' ' << v << ' ' << dcc[x] << ' ' << dcc[v] << ' ' << bridge[i] << '\n';
if (~dcc[v] || bridge[i]) continue;
// cerr << "Dfs: " << x << "->" << v << "!\n";
dfs(v);
}
}
vector<array<int, 2>> e[N];
struct Matrix {
int n;
vector<vector<Z>> a;
Matrix() {n = 0;}
void Init(int _n) {
n = _n;
a.assign(n, vector<Z>(n, 0));
}
auto &operator[](int x) {return a[x];}
int size() {return n;}
} ;
using K = Matrix;
Z det(K a) {
bool sign = 0;
Z ans = 1;
const int n = a.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
while (a[i][i].x > 0) {
Z div = a[j][i].x / a[i][i].x;
for (int k = 0; k < n; ++k)
a[j][k] -= div * a[i][k];
swap(a[i], a[j]); sign ^= 1;
}
swap(a[i], a[j]); sign ^= 1;
}
}
for (int i = 0; i < n; ++i)
ans *= a[i][i];
return sign ? -ans : ans;
}
K a[N];
int id[N], tofa[N];
Z f[N][2], g[N][2];
void dp(int x, int fa) {
// cerr << "Node " << x << ' ' << fa << ":\n";
for (auto p : vec[x]) g[p][0] = 1;
for (auto [v, fr] : e[x]) if (v != fa) {
dp(v, x);
// cerr << "ZHUANYIBIAN: " << v << ' ' << x << ' ' << fr << ' ' << g[fr][0] << ' ' << g[fr][1] << ' ' << f[v][0] << ' ' << f[v][1] << '\n';
g[fr][1] = g[fr][1] * f[v][1] - g[fr][0] * f[v][0];
g[fr][0] *= f[v][1];
} else tofa[x] = fr;
if (!~tofa[x]) tofa[x] = vec[x][0];
// cerr << x << ' ' << fa << ' ' << tofa[x] << ' ' << " ?!?!\n";
int sz = vec[x].size();
a[x].Init(sz);
for (int i = 0; i < sz; ++i) {int v = vec[x][i]; id[v] = i;}
for (auto u : vec[x]) {
for (int i = head[u]; i; i = nex[i]) {
int v = to[i]; if (bridge[i]) continue;
a[x][id[u]][id[v]] = 1;
}
}
for (int i = 0; i < sz; ++i) {
int v = vec[x][i];
a[x][i][i] = g[v][1];
for (int k = 0; k < sz; ++k)
if (k != i) a[x][i][k] *= g[v][0];
}
// cerr << sz << ' ' << "WTF\n";
f[x][1] = det(a[x]);
if (sz == 1) f[x][0] = g[vec[x][0]][0];
else {
K b; b.Init(sz - 1);
for (int i = 0, _ = -1; i < sz; ++i) {
if (vec[x][i] != tofa[x]) ++_;
for (int j = 0, __ = -1; j < sz; ++j) {
if (vec[x][j] != tofa[x]) ++__;
// cerr << "index: " << _ << ' ' << __ << '\n';
if (_ >= 0 && __ >= 0) b[_][__] = a[x][i][j];
}
}
// cerr << "Matrix B:\n";
// for (int i = 0; i < sz - 1; ++i) for (int j = 0; j < sz - 1; ++j)
// cerr << b[i][j] << " \n"[j == sz - 2];
f[x][0] = det(b) * g[tofa[x]][0];
}
// cerr <<"Debug:\n";
// cerr << x << ' ' << f[x][0] << ' ' << f[x][1] << "!\n";
// cerr << "Size: " << sz << '\n';
// for (int i = 0; i < sz; ++i) cerr << vec[x][i] << ' ' << g[vec[x][i]][0] << ' ' << g[vec[x][i]][1] << '\n';
// cerr << '\n';
// for (int i = 0; i < sz; ++i, cerr << '\n') for (int j = 0; j < sz; ++j)
// cerr << a[x][i][j] << ' ';
// cerr << "------------------\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> k;
memset(tofa, -1, sizeof tofa);
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
--u, --v; add(u, v);
}
tarjan(0, 0);
fill(dcc, dcc + n, -1);
for (int i = 0; i < n; ++i) if (!~dcc[i]) {
dfs(i);
++t;
}
for (int u = 0; u < n; ++u) {
vec[dcc[u]].push_back(u);
for (int i = head[u]; i; i = nex[i]) {
int v = to[i];
if (dcc[u] != dcc[v])
e[dcc[u]].push_back({dcc[v], u});
}
}
// for (int i = 0; i < n; ++i) cerr << dcc[i] << ' '; cerr << '\n';
// cerr << cnt << '\n';
// for (int i = 2; i <= cnt; ++i) if (bridge[i]) {
// cerr << to[i] << " \n"[i & 1];
// }
// return 0;
dp(0, 0);
cout << (n & 1 ? -1 : 1) * f[0][1] << '\n';
}
/*
10 12 3
3 5
5 9
5 10
1 2
1 3
2 3
4 5
4 6
5 6
7 8
7 9
8 9
answer: 4
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 10860kb
input:
4 3 1 1 2 2 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 11148kb
input:
6 6 3 2 3 5 6 2 5 1 2 3 4 6 2
output:
998244352
result:
ok 1 number(s): "998244352"
Test #3:
score: 0
Accepted
time: 1ms
memory: 10560kb
input:
10 15 10 1 8 1 7 6 7 2 8 6 9 1 2 4 9 4 10 4 6 5 6 3 8 9 10 8 10 3 5 2 7
output:
35
result:
ok 1 number(s): "35"
Test #4:
score: 0
Accepted
time: 0ms
memory: 10824kb
input:
10 9 1 1 2 1 3 3 4 3 5 1 6 3 7 6 8 3 9 8 10
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 6640kb
input:
1 0 1
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 1ms
memory: 10912kb
input:
10 9 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 1ms
memory: 10840kb
input:
10 12 3 3 5 5 9 5 10 1 2 1 3 2 3 4 5 4 6 5 6 7 8 7 9 8 9
output:
4
result:
ok 1 number(s): "4"
Test #8:
score: 0
Accepted
time: 1ms
memory: 11224kb
input:
10 12 3 3 5 1 8 6 10 1 2 1 3 2 3 4 5 4 6 5 6 7 8 7 9 8 9
output:
3
result:
ok 1 number(s): "3"
Test #9:
score: 0
Accepted
time: 0ms
memory: 12068kb
input:
10 11 3 1 2 1 3 1 8 1 9 3 4 3 5 4 5 6 7 6 8 7 8 9 10
output:
4
result:
ok 1 number(s): "4"
Test #10:
score: 0
Accepted
time: 0ms
memory: 10332kb
input:
10 11 3 1 2 1 3 1 6 1 9 3 4 3 5 4 5 6 7 6 8 7 8 9 10
output:
4
result:
ok 1 number(s): "4"
Test #11:
score: 0
Accepted
time: 1ms
memory: 10344kb
input:
10 15 7 2 9 1 2 1 4 1 6 1 7 2 3 2 5 2 6 3 5 4 5 4 6 5 6 8 9 8 10 9 10
output:
3
result:
ok 1 number(s): "3"
Test #12:
score: 0
Accepted
time: 0ms
memory: 10208kb
input:
10 25 7 4 10 1 2 1 3 1 4 1 5 1 6 1 7 2 3 2 4 2 5 2 6 2 7 3 4 3 5 3 6 3 7 4 5 4 6 4 7 5 6 5 7 6 7 8 9 8 10 9 10
output:
7
result:
ok 1 number(s): "7"
Test #13:
score: 0
Accepted
time: 2ms
memory: 11300kb
input:
10 12 7 1 2 1 5 1 10 3 4 3 7 3 9 4 6 4 9 5 8 6 9 7 8 8 9
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 0ms
memory: 11640kb
input:
10 24 7 1 2 1 4 1 10 3 4 3 5 3 6 3 7 3 8 3 9 4 5 4 6 4 7 4 8 4 9 5 6 5 7 5 8 5 9 6 7 6 8 6 9 7 8 7 9 8 9
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 0ms
memory: 10348kb
input:
10 18 10 1 3 1 5 1 6 1 8 1 9 2 5 2 7 2 9 3 5 3 9 3 10 4 5 4 10 5 6 6 7 6 8 7 9 8 9
output:
998244349
result:
ok 1 number(s): "998244349"
Test #16:
score: 0
Accepted
time: 1ms
memory: 10140kb
input:
10 45 10 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 5 4 6 4 7 4 8 4 9 4 10 5 6 5 7 5 8 5 9 5 10 6 7 6 8 6 9 6 10 7 8 7 9 7 10 8 9 8 10 9 10
output:
998244344
result:
ok 1 number(s): "998244344"
Test #17:
score: -100
Wrong Answer
time: 1ms
memory: 11192kb
input:
10 14 10 1 2 1 10 3 5 4 6 4 8 4 9 5 6 5 8 5 9 6 8 6 9 7 8 8 9 9 10
output:
998244351
result:
wrong answer 1st numbers differ - expected: '998244352', found: '998244351'