結果
問題 | No.2330 Eat Slime |
ユーザー |
|
提出日時 | 2023-05-28 15:30:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 280 ms / 4,000 ms |
コード長 | 14,236 bytes |
コンパイル時間 | 4,264 ms |
コンパイル使用メモリ | 210,080 KB |
実行使用メモリ | 26,916 KB |
最終ジャッジ日時 | 2024-12-27 07:05:50 |
合計ジャッジ時間 | 10,343 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;template<const unsigned int MOD> struct prime_modint {using mint = prime_modint;unsigned int v;prime_modint() : v(0) {}prime_modint(unsigned int a) { a %= MOD; v = a; }prime_modint(unsigned long long a) { a %= MOD; v = a; }prime_modint(int a) { a %= (int)(MOD); if(a < 0)a += MOD; v = a; }prime_modint(long long a) { a %= (int)(MOD); if(a < 0)a += MOD; v = a; }static constexpr int mod() { return MOD; }mint& operator++() {v++; if(v == MOD)v = 0; return *this;}mint& operator--() {if(v == 0)v = MOD; v--; return *this;}mint operator++(int) { mint result = *this; ++*this; return result; }mint operator--(int) { mint result = *this; --*this; return result; }mint& operator+=(const mint& rhs) { v += rhs.v; if(v >= MOD) v -= MOD; return *this; }mint& operator-=(const mint& rhs) { if(v < rhs.v) v += MOD; v -= rhs.v; return *this; }mint& operator*=(const mint& rhs) {v = (unsigned int)((unsigned long long)(v) * rhs.v % MOD);return *this;}mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }mint operator+() const { return *this; }mint operator-() const { return mint() - *this; }mint pow(long long n) const {assert(0 <= n);mint r = 1, x = *this;while (n) {if (n & 1) r *= x;x *= x;n >>= 1;}return r;}mint inv() const { assert(v); return pow(MOD - 2); }friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; }friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; }friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; }friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; }friend bool operator==(const mint& lhs, const mint& rhs) { return (lhs.v == rhs.v); }friend bool operator!=(const mint& lhs, const mint& rhs) { return (lhs.v != rhs.v); }friend std::ostream& operator << (std::ostream &os, const mint& rhs) noexcept { return os << rhs.v; }};//using mint = prime_modint<1000000007>;using mint = prime_modint<998244353>;constexpr int bsf_constexpr(unsigned int n) {int x = 0;while (!(n & (1 << x))) x++;return x;}template<class mint> struct fft_info {const int g = primitive_root(mint::mod());static constexpr int rank2 = bsf_constexpr(mint::mod() - 1);std::array<mint, rank2 + 1> root; // root[i]^(2^i) == 1std::array<mint, rank2 + 1> iroot; // root[i] * iroot[i] == 1std::array<mint, std::max(0, rank2 - 2 + 1)> rate2;std::array<mint, std::max(0, rank2 - 2 + 1)> irate2;std::array<mint, std::max(0, rank2 - 3 + 1)> rate3;std::array<mint, std::max(0, rank2 - 3 + 1)> irate3;fft_info() {root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);iroot[rank2] = root[rank2].inv();for (int i = rank2 - 1; i >= 0; i--) {root[i] = root[i + 1] * root[i + 1];iroot[i] = iroot[i + 1] * iroot[i + 1];}{mint prod = 1, iprod = 1;for (int i = 0; i <= rank2 - 2; i++) {rate2[i] = root[i + 2] * prod;irate2[i] = iroot[i + 2] * iprod;prod *= iroot[i + 2];iprod *= root[i + 2];}}{mint prod = 1, iprod = 1;for (int i = 0; i <= rank2 - 3; i++) {rate3[i] = root[i + 3] * prod;irate3[i] = iroot[i + 3] * iprod;prod *= iroot[i + 3];iprod *= root[i + 3];}}}int ceil_pow2(int n) {int x = 0;while ((1U << x) < (unsigned int)(n)) x++;return x;}int bsf(unsigned int n) {#ifdef _MSC_VERunsigned long index;_BitScanForward(&index, n);return index;#elsereturn __builtin_ctz(n);#endif}constexpr long long safe_mod(long long x, long long m) {x %= m;if (x < 0) x += m;return x;}constexpr long long pow_mod_constexpr(long long x, long long n, int m) {if (m == 1) return 0;unsigned int _m = (unsigned int)(m);unsigned long long r = 1;unsigned long long y = safe_mod(x, m);while (n) {if (n & 1) r = (r * y) % _m;y = (y * y) % _m;n >>= 1;}return r;}constexpr int primitive_root(int m) {if (m == 2) return 1;if (m == 167772161) return 3;if (m == 469762049) return 3;if (m == 754974721) return 11;if (m == 998244353) return 3;int divs[20] = {};divs[0] = 2;int cnt = 1;int x = (m - 1) / 2;while (x % 2 == 0) x /= 2;for (int i = 3; (long 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;for (int i = 0; i < cnt; i++) {if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {ok = false;break;}}if (ok) return g;}}void butterfly(std::vector<mint>& a) {int n = int(a.size());int h = ceil_pow2(n);int len = 0; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformedwhile (len < h) {if (h - len == 1) {int p = 1 << (h - len - 1);mint rot = 1;for (int s = 0; s < (1 << len); s++) {int offset = s << (h - len);for (int i = 0; i < p; i++) {auto l = a[i + offset];auto r = a[i + offset + p] * rot;a[i + offset] = l + r;a[i + offset + p] = l - r;}if (s + 1 != (1 << len)) rot *= rate2[bsf(~(unsigned int)(s))];}len++;} else {// 4-baseint p = 1 << (h - len - 2);mint rot = 1, imag = root[2];for (int s = 0; s < (1 << len); s++) {mint rot2 = rot * rot;mint rot3 = rot2 * rot;int offset = s << (h - len);for (int i = 0; i < p; i++) {auto mod2 = 1ULL * mint::mod() * mint::mod();auto a0 = 1ULL * a[i + offset].v;auto a1 = 1ULL * a[i + offset + p].v * rot.v;auto a2 = 1ULL * a[i + offset + 2 * p].v * rot2.v;auto a3 = 1ULL * a[i + offset + 3 * p].v * rot3.v;auto a1na3imag = 1ULL * mint(a1 + mod2 - a3).v * imag.v;auto na2 = mod2 - a2;a[i + offset] = a0 + a2 + a1 + a3;a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));a[i + offset + 2 * p] = a0 + na2 + a1na3imag;a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);}if (s + 1 != (1 << len))rot *= rate3[bsf(~(unsigned int)(s))];}len += 2;}}}void butterfly_inv(std::vector<mint>& a) {int n = int(a.size());int h = ceil_pow2(n);int len = h;while (len) {if (len == 1) {int p = 1 << (h - len);mint irot = 1;for (int s = 0; s < (1 << (len - 1)); s++) {int offset = s << (h - len + 1);for (int i = 0; i < p; i++) {auto l = a[i + offset];auto r = a[i + offset + p];a[i + offset] = l + r;a[i + offset + p] = (unsigned long long)(mint::mod() + l.v - r.v) * irot.v;}if (s + 1 != (1 << (len - 1))) irot *= irate2[bsf(~(unsigned int)(s))];}len--;} else {// 4-baseint p = 1 << (h - len);mint irot = 1, iimag = iroot[2];for (int s = 0; s < (1 << (len - 2)); s++) {mint irot2 = irot * irot;mint irot3 = irot2 * irot;int offset = s << (h - len + 2);for (int i = 0; i < p; i++) {auto a0 = 1ULL * a[i + offset + 0 * p].v;auto a1 = 1ULL * a[i + offset + 1 * p].v;auto a2 = 1ULL * a[i + offset + 2 * p].v;auto a3 = 1ULL * a[i + offset + 3 * p].v;auto a2na3iimag = 1ULL * mint((mint::mod() + a2 - a3) * iimag.v).v;a[i + offset] = a0 + a1 + a2 + a3;a[i + offset + 1 * p] = (a0 + (mint::mod() - a1) + a2na3iimag) * irot.v;a[i + offset + 2 * p] = (a0 + a1 + (mint::mod() - a2) + (mint::mod() - a3)) * irot2.v;a[i + offset + 3 * p] = (a0 + (mint::mod() - a1) + (mint::mod() - a2na3iimag)) * irot3.v;}if (s + 1 != (1 << (len - 2))) irot *= irate3[bsf(~(unsigned int)(s))];}len -= 2;}}}std::vector<mint> convolution_naive(const std::vector<mint>& a, const std::vector<mint>& b) {int n = int(a.size()), m = int(b.size());std::vector<mint> ans(n + m - 1);if (n < m) {for (int j = 0; j < m; j++) {for (int i = 0; i < n; i++) {ans[i + j] += a[i] * b[j];}}} else {for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ans[i + j] += a[i] * b[j];}}}return ans;}std::vector<mint> convolution_fft(std::vector<mint> a, std::vector<mint> b) {int n = int(a.size()), m = int(b.size());int z = 1 << ceil_pow2(n + m - 1);a.resize(z), butterfly(a);b.resize(z), butterfly(b);for (int i = 0; i < z; i++) a[i] *= b[i];butterfly_inv(a);a.resize(n + m - 1);mint iz = mint(z).inv();for (int i = 0; i < n + m - 1; i++) a[i] *= iz;return a;}};template <class mint> std::vector<mint> convolution(std::vector<mint>&& a, std::vector<mint>&& b) {int n = int(a.size()), m = int(b.size());if (!n || !m) return {};static fft_info<mint> info;if (std::min(n, m) <= 60) return info.convolution_naive(a, b);return info.convolution_fft(a, b);}template <unsigned int mod = 998244353, class T>std::vector<T> convolution(std::vector<T>& a, std::vector<T>& b) {int n = int(a.size()), m = int(b.size());if (!n || !m) return {};using mint = prime_modint<mod>;std::vector<mint> a2(n), b2(m), c2;for (int i = 0; i < n; i++) a2[i] = mint(a[i]);for (int i = 0; i < m; i++) b2[i] = mint(b[i]);static fft_info<mint> info;if (std::min(n, m) <= 60) c2 = info.convolution_naive(a2, b2);else c2 = info.convolution_fft(a2, b2);std::vector<T> c(n + m - 1);for (int i = 0; i < n + m - 1; i++) c[i] = c2[i].v;return c;}std::vector<long long> convolution_ll(std::vector<long long>& a, std::vector<long long>& b) {int n = int(a.size()), m = int(b.size());if (!n || !m) return {};auto safe_mod = [&](long long x, long long m) {x %= m;if (x < 0) x += m;return x;};static constexpr unsigned long long MOD1 = 754974721; // 2^24static constexpr unsigned long long MOD2 = 167772161; // 2^25static constexpr unsigned long long MOD3 = 469762049; // 2^26static constexpr unsigned long long M2M3 = MOD2 * MOD3;static constexpr unsigned long long M1M3 = MOD1 * MOD3;static constexpr unsigned long long M1M2 = MOD1 * MOD2;static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;static constexpr unsigned long long i1 = 190329765; //inv_gcd(MOD2 * MOD3, MOD1).secondstatic constexpr unsigned long long i2 = 58587104; //inv_gcd(MOD1 * MOD3, MOD2).secondstatic constexpr unsigned long long i3 = 187290749; //inv_gcd(MOD1 * MOD2, MOD3).secondauto c1 = convolution<MOD1>(a, b);auto c2 = convolution<MOD2>(a, b);auto c3 = convolution<MOD3>(a, b);std::vector<long long> c(n + m - 1);for (int i = 0; i < n + m - 1; i++) {unsigned long long x = 0;x += (c1[i] * i1) % MOD1 * M2M3;x += (c2[i] * i2) % MOD2 * M1M3;x += (c3[i] * i3) % MOD3 * M1M2;long long diff = c1[i] - safe_mod((long long)(x), (long long)(MOD1));if (diff < 0) diff += MOD1;static constexpr unsigned long long offset[5] = {0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};x -= offset[diff % 5];c[i] = x;}return c;}int main(){ios::sync_with_stdio(false);cin.tie(0);ll n, m, x;cin >> n >> m >> x;vector<vector<mint>> a(5, vector<mint>(n)), b(5, vector<mint>(n)), c(5);for(int i = 0; i < n; i++){int v;cin >> v;v--;a[v][n - 1 - i] = 1;}for(int i = 0; i < m; i++){int x, y, z;cin >> x >> y >> z;x--, y--;b[y][x] += z;}vector<ll> score(n + 1);score[n] = n * x;for(int i = 0; i < n; i++){score[i] += i * x;}for(int i = 0; i < 5; i++){c[i] = convolution(a[i], b[i]);for(int j = n - 1; j >= 0; j--){score[j] += c[i][(n - 1) - j].v;}}cout << *max_element(score.begin(), score.end()) << '\n';}