結果
| 問題 |
No.1784 Not a star yet...
|
| ユーザー |
 Jerry Rowe (cooluo)
|
| 提出日時 | 2025-06-08 22:29:15 |
| 言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 831 ms / 2,000 ms |
| コード長 | 11,269 bytes |
| コンパイル時間 | 7,389 ms |
| コンパイル使用メモリ | 172,236 KB |
| 実行使用メモリ | 68,864 KB |
| 最終ジャッジ日時 | 2025-06-08 22:29:49 |
| 合計ジャッジ時間 | 30,647 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 61 |
コンパイルメッセージ
main.cpp:327:13: warning: left operand of comma operator has no effect [-Wunused-value]
327 | dbg(i, j, p1, p2, p3, p4, b);
| ^
main.cpp:49:19: note: expanded from macro 'dbg'
49 | #define dbg(...) (__VA_ARGS__)
| ^~~~~~~~~~~
main.cpp:327:16: warning: left operand of comma operator has no effect [-Wunused-value]
327 | dbg(i, j, p1, p2, p3, p4, b);
| ^
main.cpp:49:19: note: expanded from macro 'dbg'
49 | #define dbg(...) (__VA_ARGS__)
| ^~~~~~~~~~~
main.cpp:327:19: warning: left operand of comma operator has no effect [-Wunused-value]
327 | dbg(i, j, p1, p2, p3, p4, b);
| ^~
main.cpp:49:19: note: expanded from macro 'dbg'
49 | #define dbg(...) (__VA_ARGS__)
| ^~~~~~~~~~~
main.cpp:327:23: warning: left operand of comma operator has no effect [-Wunused-value]
327 | dbg(i, j, p1, p2, p3, p4, b);
| ^~
main.cpp:49:19: note: expanded from macro 'dbg'
49 | #define dbg(...) (__VA_ARGS__)
| ^~~~~~~~~~~
main.cpp:327:27: warning: left operand of comma operator has no effect [-Wunused-value]
327 | dbg(i, j, p1, p2, p3, p4, b);
| ^~
main.cpp:49:19: note: expanded from macro 'dbg'
49 | #define dbg(...) (__VA_ARGS__)
| ^~~~~~~~~~~
main.cpp:327:31: warning: left operand of comma operator has no effect [-Wunused-value]
327 | dbg(i, j, p1, p2, p3, p4, b);
| ^~
main.cpp:49:19: note: expanded from macro 'dbg'
49 | #define dbg(...) (__VA_ARGS__)
| ^~~~~~~~~~~
main.cpp:327:35: warning: expression result unused [-Wunused-value]
327 | dbg(i, j, p1, p2, p3, p4, b);
| ^
main.cpp:49:19: note: expanded from macro 'dbg'
49 | #define dbg(...) (__VA_ARGS__)
|
ソースコード
#include <bits/stdc++.h>
// #include <bits/extc++.h>
using namespace std;
#define ll long long
#define ul unsigned ll
#define LL __int128_t
#define UL __uint128_t
#define db double
#define DB long db
#define pii pair<int, int>
#define fi first
#define se second
#define mkpr make_pair
#define vi vector<int>
#define vmi vector<mint>
#define vii vector<pii>
#define rsz resize
#define ep emplace
#define pb pop_back
#define eb emplace_back
#define all(c) (c).begin(), (c).end()
#define disc(c) (sort(all(c)), (c).rsz(unique(all(c)) - (c).begin()))
#define ers(S, x) ((S).erase((S).find(x)))
#define bit(k) (1u << (k))
#define Bit(k) (1ull << (k))
#define BIT(k) ((UL)1 << (k))
#define lowbit(x) ((x) & -(x))
#define bin(s, k) ((s) >> (k) & 1)
#define lg2(x) (31 - __builtin_clz(x))
#define LG2(x) (63 - __builtin_clzll(x))
#define highbit(x) bit(lg2(x))
#define highbitll(x) Bit(LG2(x))
#define popcnt(x) __builtin_popcount(x)
#define popcntll(x) __builtin_popcountll(x)
#define mem(a, x) memset(a, x, sizeof(a))
#define req(i, l, r) for (int i(l), i##End(r); i < i##End; i = -~i)
#define qer(i, r, l) for (int i(r), i##End(l); i > i##End; i = ~-i)
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)
#define per(i, r, l) for (int i(r), i##End(l); i >= i##End; i = ~-i)
// #define FILERR
#ifdef JYR
#include "debug.h"
#define errm(x, ...) fprintf(stderr, x, ##__VA_ARGS__)
#define errs(x, ...) errm(x "\n", ##__VA_ARGS__)
#else
#define dbg(...) (__VA_ARGS__)
#define dbgArr(...) (__VA_ARGS__)
#define errm(x, ...) (x, ##__VA_ARGS__)
#define errs(x, ...) (x, ##__VA_ARGS__)
#endif
#define __
template<typename T, typename U> void chkmx(T &_a, U _b) { if (_a < _b) _a = _b; }
template<typename T, typename U> void chkmn(T &_a, U _b) { if (_b < _a) _a = _b; }
template<typename T, typename U> T OxO(T _a, U _b) { return _a >= _b ? -1 : _a; }
bool Mbe;
template <int MOD> struct modint {
int num;
const static __uint128_t brt = ((__uint128_t)(1) << (64)) / MOD;
modint() { num = 0; }
modint(int x) { num = x % MOD; }
modint(ll x) { num = x % MOD; }
modint<MOD> operator=(int x) {
num = x % MOD;
return (*this);
}
modint<MOD> operator=(ll x) {
num = x % MOD;
return (*this);
}
modint<MOD> operator+(modint<MOD> c) const {
ll x = num + c.num;
return x >= MOD ? x - MOD : x;
}
template <typename T> modint<MOD> operator+(T c) const {
return (*this) + modint<MOD>(c);
}
modint<MOD> operator-(modint<MOD> c) const {
ll x = num - c.num;
return x < 0 ? x + MOD : x;
}
template <typename T> modint<MOD> operator-(T c) const {
return (*this) - modint<MOD>(c);
}
modint<MOD> operator*(modint<MOD> c) const {
ll x = (ll)num * c.num;
x = x - MOD * (brt * x >> 64);
while (x >= MOD) x -= MOD;
return x;
}
template <typename T> modint<MOD> operator*(T c) const {
return (*this) * modint<MOD>(c);
}
modint<MOD> qpow(ll b) const {
modint<MOD> ml = 1, bs = *this;
while (b) {
if (b & 1) ml *= bs;
bs *= bs, b >>= 1;
} return ml;
}
modint<MOD> inv() const { return qpow(MOD - 2); }
modint<MOD> operator/(modint<MOD> c) const { return (*this) * c.inv(); }
template <typename T> modint<MOD> operator/(T c) const {
return (*this) / modint<MOD>(c);
}
// operator int() { return num; }
modint<MOD> operator+=(modint<MOD> c) { return (*this) = (*this) + c; }
modint<MOD> operator-=(modint<MOD> c) { return (*this) = (*this) - c; }
template <typename T> modint<MOD> operator*=(T c) {
return (*this) = (*this) * c;
}
modint<MOD> operator/=(modint<MOD> c) { return (*this) = (*this) / c; }
modint<MOD> operator-() { return MOD - num; }
friend ostream& operator<<(ostream& w, modint<MOD> x) {
w << x.num;
return w;
}
friend istream& operator>>(istream& w, modint<MOD> x) {
w >> x.num;
x.num %= MOD;
return w;
}
bool operator==(modint<MOD> x) { return num == x.num; }
};
template <typename T, int MOD>
modint<MOD> operator*(T a, modint<MOD> b) { return b * a; }
template <typename T, int MOD>
modint<MOD> operator/(T a, modint<MOD> b) { return b.inv() * a; }
struct FastIO {
char buf[1 << 20], *p1, *p2;
char puf[1 << 20], *pf;
FastIO() : p1(buf), p2(buf), pf(puf) {}
~FastIO() { fwrite(puf, 1, pf - puf, stdout); }
char gc() {
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin);
return p1 == p2 ? EOF : *p1++;
}
bool blank(char c) { return c == ' ' || c == '\r' || c == '\n' || c == '\t'; }
char rd() {
char c = gc(); while (blank(c)) c = gc();
return c;
}
template<typename T> T rd() {
T x = 0; int f = 0; char c = gc();
while (!isdigit(c)) f = (c == '-'), c = gc();
while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
return f ? -x : x;
}
int rds(char *s) {
char c = gc(), *S = s;
while (blank(c)) c = gc();
while (!blank(c) && c != EOF) *s++ = c, c = gc();
return *s = 0, abs(s - S);
}
int rdl(char *s) {
char c = gc(), *S = s;
while (c == '\r' || c == '\n') c = gc();
while (c != '\r' && c != '\n' && c != EOF) *s++ = c, c = gc();
return *s = 0, abs(s - S);
}
void rd(char &c) { c = rd(); }
void rd(char *s) {
char c = gc();
while (blank(c)) c = gc();
if (c == EOF) { *s = 0; return; }
while (!blank(c) && c != EOF) *s++ = c, c = gc();
*s = 0;
}
void rd(string &s) {
char c = gc(); s = "";
while (blank(c)) c = gc();
if (c == EOF) return;
while (!blank(c) && c != EOF) s += c, c = gc();
}
template<int MOD> void rd(modint<MOD> &x) { x = rd<int>(); }
template<typename T> void rd(T &x) {
x = 0; int f = 0; char c = gc();
while (!isdigit(c)) f = (c == '-'), c = gc();
while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
if (f) x = -x;
}
template<typename T, typename... Ts>
void rd(T& x, Ts&... xs) { rd(x), rd(xs...); }
template<typename T>
void rda(T* x, int l, int r) { rep(i, l, r) rd(x[i]); }
template<typename T>
void rda(T* x, int n) { rep(i, 1, n) rd(x[i]); }
void pc(const char &c) {
if (pf - puf == 1 << 20) fwrite(pf = puf, 1, 1 << 20, stdout);
*pf++ = c;
}
void prt(char c) { pc(c); }
void prt(char* s) { while (*s) pc(*s++); }
void prt(const char* s) { while (*s) pc(*s++); }
void prt(bool b) { pc(b ? '1' : '0'); }
void prt(string s) { for (auto &&c : s) pc(c); }
template<typename T> void prt(T x) {
static int st[41], tp = 0;
if (x == 0) { pc('0'); return; }
if (x < 0) x = -x, pc('-');
while (x) st[++tp] = x % 10, x /= 10;
while (tp) pc(st[tp--] + '0');
}
template<int MOD> void prt(modint<MOD> x) { prt(x.num); }
template<typename T> void prt(T *x) { while (*x) pc(*x++); }
template<typename T, typename... Ts>
void prt(T x, Ts... xs) { prt(x), prt(xs...); }
template<typename T> void prb(T x) { prt(x, ' '); }
template<typename T> void prt(vector<T> vt) { for (auto x : vt) prb(x); }
template<typename T, typename... Ts>
void prb(T x, Ts... xs) { prt(x, ' '), prb(xs...); }
template<typename T> void prd(T x) { prt(x, '\n'); }
template<typename T, typename... Ts>
void prd(T x, Ts... xs) { prt(x, ' '), prd(xs...); }
} IO;
#define rd IO.rd
#define rda IO.rda
#define rds IO.rds
#define rdl IO.rdl
#define ri rd<int>()
#define rl rd<ll>()
#define prt IO.prt
#define prs(...) prt(__VA_ARGS__, '\n')
#define prb IO.prb
#define prd IO.prd
#define edl IO.pc('\n')
// #define MC
#define N 255
#define mod 998244353
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using Z = modint<mod>;
int n;
Z ans;
int d0[N], X;
int d1[N], Y;
Z c[N][N][N];
Z a[N][N];
Z f[N][N];
int id(int i, int j) { return i * (Y + 1) + j; }
void Gauss() {
rep(i, 0, Y) {
int p = i;
while (a[p][i] == 0) p++;
if (i != p) swap(a[i], a[p]);
rep(j, 0, Y) if (i != j) {
Z x = a[j][i] / a[i][i];
rep(k, i, Y + 1) a[j][k] -= a[i][k] * x;
}
}
}
void add(Z z[], int I, int J, Z p) {
rep(k, 0, Y + 1) z[k] += c[I][J][k] * p;
}
void mslv() {
req(i, 1, n = ri) {
int u, v, w; rd(u, v, w);
if (w == 1) X++, d0[u]++, d0[v]++;
else Y++, d1[u]++, d1[v]++;
}
Z P = Z(n - 1) * n / 2 - (n - 2);
rep(i, 0, Y) c[0][i][i] = 1;
req(i, 0, X) rep(j, 0, Y) {
Z Q = n - i - j;
Z p1 = i * (P - Q);
Z p2 = 2 * j * (P - Q);
Z p3 = (X - i) * (Q - 1);
Z p4 = 2 * (Y - j) * (Q - 1);
Z b = P * (i + j * 2) / 2;
// int u = id(i, j);
// a[u][u] = p1 + p2 + p3 + p4;
// if (i) a[u][id(i - 1, j)] = -p1;
// if (j) a[u][id(i, j - 1)] = -p2;
// if (i != X) a[u][id(i + 1, j)] = -p3;
// if (j != Y) a[u][id(i, j + 1)] = -p4;
// a[u][id(X, Y) + 1] = b;
add(c[i + 1][j], i, j, p1 + p2 + p3 + p4);
if (i) add(c[i + 1][j], i - 1, j, -p1);
if (j) add(c[i + 1][j], i, j - 1, -p2);
if (j != Y) add(c[i + 1][j], i, j + 1, -p4);
c[i + 1][j][Y + 1] -= b;
dbg(i, j, p1, p2, p3, p4, b);
rep(k, 0, Y + 1) c[i + 1][j][k] /= p3;
}
for (int i = X, j = 0; j < Y; j++) {
Z Q = n - i - j;
Z p1 = i * (P - Q);
Z p2 = 2 * j * (P - Q);
Z p3 = (X - i) * (Q - 1);
Z p4 = 2 * (Y - j) * (Q - 1);
Z b = P * (i + j * 2) / 2;
add(a[j], i, j, p1 + p2 + p3 + p4);
if (i) add(a[j], i - 1, j, -p1);
if (j) add(a[j], i, j - 1, -p2);
add(a[j], i, j + 1, -p4);
a[j][Y + 1] = b - a[j][Y + 1];
} a[Y][0] = 1;
rep(i, 0, Y) dbgArr(a[i], 0, Y + 1);
Gauss(), f[0][Y + 1] = 1;
rep(j, 0, Y) f[0][j] = a[j][Y + 1] / a[j][j];
rep(i, 1, X) rep(j, 0, Y) rep(k, 0, Y + 1) f[i][j] += c[i][j][k] * f[0][k];
rep(i, 0, X) rep(j, 0, Y) dbg(i, j, f[i][j]), dbgArr(c[i][j], 0, Y + 1);
rep(i, 1, n) ans += f[d0[i]][d1[i]];
prs(ans - f[X][Y] - X * f[1][0] - Y * f[0][1]);
}
/*
p1p2p3p4f[i][j] - p1f[i-1][j] - p2f[i][j-1] - p3f[i+1][j] - p4f[i][j+1] = b
f[i+1][j] = (p1p2p3p4f[i][j] - p1f[i-1][j] - p2f[i][j-1] - p4f[i][j+1] - b)/p3
*/
void mprw() {}
bool Med;
int main() {
#ifdef JYR
errs("\033[1;34mRunning!\033[0;m");
freopen("Test.in", "r", stdin);
freopen("Test.out", "w", stdout);
#ifdef FILERR
freopen("Test.err", "w", stderr);
#endif
#endif
mprw();
#ifdef MC
int _ = ri;
while (_--) errs("------------------------------"), mslv();
errs("------------------------------");
#else
mslv();
#endif
#ifdef JYR
errm("%.3lfMB ", abs(&Med - &Mbe) / 1048576.);
errm("%.0lfms\n", clock() * 1000. / CLOCKS_PER_SEC);
#endif
return 0;
}