結果
問題 | No.2378 Cards and Subsequences |
ユーザー |
![]() |
提出日時 | 2023-06-11 15:56:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 130 ms / 2,000 ms |
コード長 | 15,708 bytes |
コンパイル時間 | 2,926 ms |
コンパイル使用メモリ | 220,356 KB |
最終ジャッジ日時 | 2025-02-14 01:50:42 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>#include <cassert>using namespace std;using ll = long long int;using pll = pair<ll, ll>;// #include <atcoder/all>// using namespace atcoder;#define REP(i, a, b) for (ll i = (a); i < (b); i++)#define REPrev(i, a, b) for (ll i = (a); i >= (b); i--)#define ALL(coll) (coll).begin(), (coll).end()#define SIZE(v) ((ll)((v).size()))#define REPOUT(i, a, b, exp, sep) REP(i, (a), (b)) cout << (exp) << (i + 1 == (b) ? "" : (sep)); cout << "\n"// @@ !! LIM(mod cmpNaive)// ---- inserted library file algOp.cc// Common definitions// zero, one, inversetemplate<typename T>constexpr T zero(const T& t) {if constexpr (is_integral_v<T> || is_floating_point_v<T>) { return (T)0; }else { return t.zero(); }}template<typename T>constexpr T one(const T& t) {if constexpr (is_integral_v<T> || is_floating_point_v<T>) { return (T)1; }else { return t.one(); }}template<typename T>constexpr T inverse(const T& t) {if constexpr (is_floating_point_v<T>) { return 1.0 / t; }else { return t.inverse(); }}// begin -- detection ideom// cf. https://blog.tartanllama.xyz/detection-idiom/namespace detail {template <template <class...> class Trait, class Enabler, class... Args>struct is_detected : false_type{};template <template <class...> class Trait, class... Args>struct is_detected<Trait, void_t<Trait<Args...>>, Args...> : true_type{};}template <template <class...> class Trait, class... Args>using is_detected = typename detail::is_detected<Trait, void, Args...>::type;// end -- detection ideomtemplate<typename T>// using subst_add_t = decltype(T::subst_add(declval<typename T::value_type &>(), declval<typename T::value_type>()));using subst_add_t = decltype(T::subst_add);template<typename T>using has_subst_add = is_detected<subst_add_t, T>;template<typename T>using add_t = decltype(T::add);template<typename T>using has_add = is_detected<add_t, T>;template<typename T>using subst_mult_t = decltype(T::subst_mult);template<typename T>using has_subst_mult = is_detected<subst_mult_t, T>;template<typename T>using mult_t = decltype(T::mult);template<typename T>using has_mult = is_detected<mult_t, T>;template<typename T>using subst_subt_t = decltype(T::subst_subt);template<typename T>using has_subst_subt = is_detected<subst_subt_t, T>;template<typename T>using subt_t = decltype(T::subt);template<typename T>using has_subt = is_detected<subt_t, T>;template <typename Opdef>struct MyAlg {using T = typename Opdef::value_type;using value_type = T;T v;MyAlg() {}MyAlg(const T& v_) : v(v_) {}MyAlg(T&& v_) : v(move(v_)) {}bool operator==(MyAlg o) const { return v == o.v; }bool operator!=(MyAlg o) const { return v != o.v; }operator T() const { return v; }MyAlg zero() const { return MyAlg(Opdef::zero(v)); }MyAlg one() const { return MyAlg(Opdef::one(v)); }MyAlg inverse() const { return MyAlg(Opdef::inverse(v)); }MyAlg operator/=(const MyAlg& o) { return *this *= o.inverse(); }MyAlg operator/(const MyAlg& o) const { return (*this) * o.inverse(); }MyAlg operator-() const { return zero() - *this; }MyAlg& operator +=(const MyAlg& o) {if constexpr (has_subst_add<Opdef>::value) {Opdef::subst_add(v, o.v);return *this;}else if constexpr (has_add<Opdef>::value) {v = Opdef::add(v, o.v);return *this;}else static_assert("either subst_add or add is needed.");}MyAlg operator +(const MyAlg& o) const {if constexpr (has_add<Opdef>::value) {return MyAlg(Opdef::add(v, o.v));}else if constexpr (has_subst_add<Opdef>::value) {MyAlg ret(v);Opdef::subst_add(ret.v, o.v);return ret;}else static_assert("either subst_add or add is needed.");}MyAlg& operator *=(const MyAlg& o) {if constexpr (has_subst_mult<Opdef>::value) {Opdef::subst_mult(v, o.v);return *this;}else if constexpr (has_mult<Opdef>::value) {v = Opdef::mult(v, o.v);return *this;}else static_assert("either subst_mult or mult is needed.");}MyAlg operator *(const MyAlg& o) const {if constexpr (has_mult<Opdef>::value) {return MyAlg(Opdef::mult(v, o.v));}else if constexpr (has_subst_mult<Opdef>::value) {MyAlg ret(v);Opdef::subst_mult(ret.v, o.v);return ret;}else static_assert("either subst_mult or mult is needed.");}MyAlg& operator -=(const MyAlg& o) {if constexpr (has_subst_subt<Opdef>::value) {Opdef::subst_subt(v, o.v);return *this;}else if constexpr (has_subt<Opdef>::value) {v = Opdef::subt(v, o.v);return *this;}else static_assert("either subst_subt or subt is needed.");}MyAlg operator -(const MyAlg& o) const {if constexpr (has_subt<Opdef>::value) {return MyAlg(Opdef::subt(v, o.v));}else if constexpr (has_subst_subt<Opdef>::value) {MyAlg ret(v);Opdef::subst_subt(ret.v, o.v);return ret;}else static_assert("either subst_subt or subt is needed.");}friend istream& operator >>(istream& is, MyAlg& t) { is >> t.v; return is; }friend ostream& operator <<(ostream& os, const MyAlg& t) { os << t.v; return os; }};// ---- end algOp.cc// ---- inserted function f:gcd from util.cc// auto [g, s, t] = eGCD(a, b)// g == gcd(|a|, |b|) and as + bt == g// |a| and |b| must be less than 2^31.tuple<ll, ll, ll> eGCD(ll a, ll b) {#if DEBUGif (abs(a) >= (1LL << 31) or abs(b) >= (1LL << 31)) throw runtime_error("eGCD: not within the range");#endifarray<ll, 50> vec; // Sufficiently large for a, b < 2^31.ll idx = 0;while (a != 0) {ll x = b / a;ll y = b % a;vec[idx++] = x;b = a;a = y;}ll g, s, t;if (b < 0) { g = -b; s = 0; t = -1; }else { g = b; s = 0; t = 1; }while (idx > 0) {ll x = vec[--idx];ll old_t = t;t = s;s = old_t - x * s;}return {g, s, t};}pair<ll, ll> crt_sub(ll a1, ll x1, ll a2, ll x2) {// DLOGKL("crt_sub", a1, x1, a2, x2);a1 = a1 % x1;a2 = a2 % x2;auto [g, s, t] = eGCD(x1, -x2);ll gq = (a2 - a1) / g;ll gr = (a2 - a1) % g;if (gr != 0) return {-1, -1};s *= gq;t *= gq;ll z = x1 / g * x2;// DLOGK(z);s = s % (x2 / g);ll r = (x1 * s + a1) % z;// DLOGK(r);if (r < 0) r += z;// DLOGK(r);return {r, z};};// Chinese Remainder Theorem//// r = crt(a1, x1, a2, x2)// ==> r = a1 (mod x1); r = a2 (mod x2); 0 <= r < lcm(x1, x2)// If no such r exists, returns -1// Note: x1 and x2 should >= 1. a1 and a2 can be negative or zero.//// r = crt(as, xs)// ==> for all i. r = as[i] (mod xs[i]); 0 <= r < lcm(xs)// If no such r exists, returns -1// Note: xs[i] should >= 1. as[i] can be negative or zero.// It should hold: len(xs) == len(as) > 0ll crt(ll a1, ll x1, ll a2, ll x2) { return crt_sub(a1, x1, a2, x2).first; }ll crt(vector<ll> as, vector<ll> xs) {// DLOGKL("crt", as, xs);assert(xs.size() == as.size() && xs.size() > 0);ll r = as[0];ll z = xs[0];for (size_t i = 1; i < xs.size(); i++) {// DLOGK(i, r, z, as[i], xs[i]);tie(r, z) = crt_sub(r, z, as[i], xs[i]);// DLOGK(r, z);if (r == -1) return -1;}return r;}// ---- end f:gcd// ---- inserted library file mod.cctemplate<int mod=0>struct FpG { // G for Generalstatic ll dyn_mod;static ll getMod() {if (mod == 0) return dyn_mod;else return mod;}static void setMod(ll _mod) { // effective only when mod == 0dyn_mod = _mod;}static ll _conv(ll x) {if (x >= getMod()) return x % getMod();if (x >= 0) return x;if (x >= -getMod()) return x + getMod();ll y = x % getMod();if (y == 0) return 0;return y + getMod();}ll val;FpG(int t = 0) : val(_conv(t)) {}FpG(ll t) : val(_conv(t)) {}FpG(const FpG& t) : val(t.val) {}FpG& operator =(const FpG& t) { val = t.val; return *this; }FpG& operator =(ll t) { val = _conv(t); return *this; }FpG& operator =(int t) { val = _conv(t); return *this; }FpG& operator +=(const FpG& t) {val += t.val;if (val >= getMod()) val -= getMod();return *this;}FpG& operator -=(const FpG& t) {val -= t.val;if (val < 0) val += getMod();return *this;}FpG& operator *=(const FpG& t) {val = (val * t.val) % getMod();return *this;}FpG inv() const {if (val == 0) { throw runtime_error("FpG::inv(): called for zero."); }auto [g, u, v] = eGCD(val, getMod());if (g != 1) { throw runtime_error("FpG::inv(): not co-prime."); }return FpG(u);}FpG zero() const { return (FpG)0; }FpG one() const { return (FpG)1; }FpG inverse() const { return inv(); }FpG& operator /=(const FpG& t) {return (*this) *= t.inv();}FpG operator +(const FpG& t) const { return FpG(val) += t; }FpG operator -(const FpG& t) const { return FpG(val) -= t; }FpG operator *(const FpG& t) const { return FpG(val) *= t; }FpG operator /(const FpG& t) const { return FpG(val) /= t; }FpG operator -() const { return FpG(-val); }bool operator ==(const FpG& t) const { return val == t.val; }bool operator !=(const FpG& t) const { return val != t.val; }operator ll() const { return val; }friend FpG operator +(int x, const FpG& y) { return FpG(x) + y; }friend FpG operator -(int x, const FpG& y) { return FpG(x) - y; }friend FpG operator *(int x, const FpG& y) { return FpG(x) * y; }friend FpG operator /(int x, const FpG& y) { return FpG(x) / y; }friend bool operator ==(int x, const FpG& y) { return FpG(x) == y; }friend bool operator !=(int x, const FpG& y) { return FpG(x) != y; }friend FpG operator +(ll x, const FpG& y) { return FpG(x) + y; }friend FpG operator -(ll x, const FpG& y) { return FpG(x) - y; }friend FpG operator *(ll x, const FpG& y) { return FpG(x) * y; }friend FpG operator /(ll x, const FpG& y) { return FpG(x) / y; }friend bool operator ==(ll x, const FpG& y) { return FpG(x) == y; }friend bool operator !=(ll x, const FpG& y) { return FpG(x) != y; }friend FpG operator +(const FpG& x, int y) { return x + FpG(y); }friend FpG operator -(const FpG& x, int y) { return x - FpG(y); }friend FpG operator *(const FpG& x, int y) { return x * FpG(y); }friend FpG operator /(const FpG& x, int y) { return x / FpG(y); }friend bool operator ==(const FpG& x, int y) { return x == FpG(y); }friend bool operator !=(const FpG& x, int y) { return x != FpG(y); }friend FpG operator +(const FpG& x, ll y) { return x + FpG(y); }friend FpG operator -(const FpG& x, ll y) { return x - FpG(y); }friend FpG operator *(const FpG& x, ll y) { return x * FpG(y); }friend FpG operator /(const FpG& x, ll y) { return x / FpG(y); }friend bool operator ==(const FpG& x, ll y) { return x == FpG(y); }friend bool operator !=(const FpG& x, ll y) { return x != FpG(y); }friend istream& operator>> (istream& is, FpG& t) {ll x; is >> x;t = x;return is;}friend ostream& operator<< (ostream& os, const FpG& t) {os << t.val;return os;}};template<int mod>ll FpG<mod>::dyn_mod;template<typename T>class Comb {int nMax;vector<T> vFact;vector<T> vInvFact;public:Comb(int nm) : nMax(nm), vFact(nm+1), vInvFact(nm+1) {vFact[0] = 1;for (int i = 1; i <= nMax; i++) vFact[i] = i * vFact[i-1];vInvFact.at(nMax) = (T)1 / vFact[nMax];for (int i = nMax; i >= 1; i--) vInvFact[i-1] = i * vInvFact[i];}T fact(int n) { return vFact[n]; }T binom(int n, int r) {if (r < 0 || r > n) return (T)0;return vFact[n] * vInvFact[r] * vInvFact[n-r];}T binom_dup(int n, int r) { return binom(n + r - 1, r); }// The number of permutation extracting r from n.T perm(int n, int r) {return vFact[n] * vInvFact[n-r];}};constexpr int primeA = 1'000'000'007;constexpr int primeB = 998'244'353; // 'using FpA = FpG<primeA>;using FpB = FpG<primeB>;// ---- end mod.cc// ---- inserted library file cmpNaive.ccconst string end_mark("^__=end=__^");int naive(istream& cin, ostream& cout);int body(istream& cin, ostream& cout);void cmpNaive() {while (true) {string s;getline(cin, s);bool run_body;if (s.at(0) == 'Q') {return;}else if (s.at(0) == 'B') {run_body = true;}else if (s.at(0) == 'N') {run_body = false;}else {cerr << "Unknown body/naive specifier.\n";exit(1);}string input_s;while (true) {getline(cin, s);if (s == end_mark) break;input_s += s;input_s += "\n";}stringstream ss_in(move(input_s));stringstream ss_out;if (run_body) {body(ss_in, ss_out);}else {naive(ss_in, ss_out);}cout << ss_out.str() << end_mark << endl;}}int main(int argc, char *argv[]) {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout << setprecision(20);#if CMPNAIVEif (argc == 2) {if (strcmp(argv[1], "cmpNaive") == 0) {cmpNaive();}else if (strcmp(argv[1], "naive") == 0) {naive(cin, cout);}else if (strcmp(argv[1], "skip") == 0) {exit(0);}else {cerr << "Unknown argument.\n";exit(1);}}else {#endifbody(cin, cout);#if CMPNAIVE}#endifreturn 0;}/*int naive(istream& cin, ostream& cout) {return 0;}int body(istream& cin, ostream& cout) {return 0;}*/// ---- end cmpNaive.cc// @@ !! LIM -- end mark --using Fp = FpB;int naive(istream& cin, ostream& cout) {ll N, M, K; cin >> N >> M >> K;// @InpVec(N, S, dec=1) [g4wxY1Py]auto S = vector(N, ll());for (int i = 0; i < N; i++) { ll v; cin >> v; v -= 1; S[i] = v; }// @End [g4wxY1Py]// @InpVec(M, A) [FXyO4M1M]auto A = vector(M, ll());for (int i = 0; i < M; i++) { ll v; cin >> v; A[i] = v; }// @End [FXyO4M1M]// @InpVec(M, B) [R7myUDlK]auto B = vector(M, ll());for (int i = 0; i < M; i++) { ll v; cin >> v; B[i] = v; }// @End [R7myUDlK]ll ans = 0;set<vector<ll>> seen;REP(x, 1, 1LL << N) {vector<ll> vec;REP(i, 0, N) if (x >> i & 1) vec.push_back(S[i]);if (seen.find(vec) != seen.end()) continue;seen.insert(vec);ll sz = SIZE(vec);REP(y, 0, 1LL << sz) {ll s = 0;REP(i, 0, sz) {if (y >> i & 1) s += A[vec[i]];else s += B[vec[i]];}if (s == K) ans++;}}cout << ans << endl;return 0;}int body(istream& cin, ostream& cout) {ll N, M, K; cin >> N >> M >> K;// @InpVec(N, S, dec=1) [g4wxY1Py]auto S = vector(N, ll());for (int i = 0; i < N; i++) { ll v; cin >> v; v -= 1; S[i] = v; }// @End [g4wxY1Py]// @InpVec(M, A) [FXyO4M1M]auto A = vector(M, ll());for (int i = 0; i < M; i++) { ll v; cin >> v; A[i] = v; }// @End [FXyO4M1M]// @InpVec(M, B) [R7myUDlK]auto B = vector(M, ll());for (int i = 0; i < M; i++) { ll v; cin >> v; B[i] = v; }// @End [R7myUDlK]vector<ll> prev(N);{vector<ll> rec(M + 1, -1LL);REP(i, 0, N) {prev[i] = rec[S[i]];rec[S[i]] = i;}}vector tbl(N, vector(K + 1, Fp(0)));vector acc(N + 1, vector(K + 1, Fp(0)));acc[0][0] = 1;REP(i, 0, N) {acc[i + 1] = acc[i];REP(k, 0, K + 1) {Fp exc = prev[i] < 0 ? Fp(0) : acc[prev[i]][k];Fp v = acc[i][k] - exc;auto op = [&](ll a) -> void {if (a <= K) {tbl[i][a] = v;acc[i + 1][a] += v;}};op(k + A[S[i]]);op(k + B[S[i]]);}}cout << acc[N][K] << endl;return 0;}