結果

問題 No.2378 Cards and Subsequences
ユーザー yamate11yamate11
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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, inverse
template<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 ideom
template<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 DEBUG
if (abs(a) >= (1LL << 31) or abs(b) >= (1LL << 31)) throw runtime_error("eGCD: not within the range");
#endif
array<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) > 0
ll 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.cc
template<int mod=0>
struct FpG { // G for General
static ll dyn_mod;
static ll getMod() {
if (mod == 0) return dyn_mod;
else return mod;
}
static void setMod(ll _mod) { // effective only when mod == 0
dyn_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.cc
const 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 CMPNAIVE
if (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 {
#endif
body(cin, cout);
#if CMPNAIVE
}
#endif
return 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0