結果
問題 | No.2215 Slide Subset Sum |
ユーザー |
👑 |
提出日時 | 2023-02-13 18:15:37 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 18,179 bytes |
コンパイル時間 | 4,113 ms |
コンパイル使用メモリ | 250,728 KB |
実行使用メモリ | 11,940 KB |
最終ジャッジ日時 | 2024-07-16 11:38:00 |
合計ジャッジ時間 | 11,077 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 283 ms
6,816 KB |
testcase_01 | TLE | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
ソースコード
#line 1 "A.cpp" #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; template <class T> using pq = priority_queue<T>; template <class T> using qp = priority_queue<T, vector<T>, greater<T>>; #define vec(T, A, ...) vector<T> A(__VA_ARGS__); #define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__)); #define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__))); #define endl "\n" #define spa ' ' #define len(A) A.size() #define all(A) begin(A), end(A) #define fori1(a) for(ll _ = 0; _ < (a); _++) #define fori2(i, a) for(ll i = 0; i < (a); i++) #define fori3(i, a, b) for(ll i = (a); i < (b); i++) #define fori4(i, a, b, c) for(ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c)) #define overload4(a, b, c, d, e, ...) e #define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__) template <typename T> vector<tuple<ll, T>> ENUMERATE(vector<T> &A, ll s = 0){ vector<tuple<ll, T>> ret(A.size()); for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]}; return ret; } vector<tuple<ll, char>> ENUMERATE(string &A, ll s = 0){ vector<tuple<ll, char>> ret(A.size()); for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]}; return ret; } #define enum1(A) fori(A.size()) #define enum2(a, A) for(auto a:A) #define enum3(i, a, A) for(auto&& [i, a]: ENUMERATE(A)) #define enum4(i, a, A, s) for(auto&& [i, a]: ENUMERATE(A, s)) #define enum(...) overload4(__VA_ARGS__, enum4, enum3, enum2, enum1)(__VA_ARGS__) template <typename T, typename S> vector<tuple<T, S>> ZIP(vector<T> &A, vector<S> &B){ int n = min(A.size(), B.size()); vector<tuple<T, S>> ret(n); for(int i = 0; i < n; i++) ret[i] = {A[i], B[i]}; return ret; } template <typename T, typename S> vector<tuple<ll, T, S>> ENUMZIP(vector<T> &A, vector<S> &B, ll s = 0){ int n = min(A.size(), B.size()); vector<tuple<ll, T, S>> ret(n); for(int i = 0; i < n; i++) ret[i] = {i + s, A[i], B[i]}; return ret; } #define zip4(a, b, A, B) for(auto&& [a, b]: ZIP(A, B)) #define enumzip5(i, a, b, A, B) for(auto&& [i, a, b]: ENUMZIP(A, B)) #define enumzip6(i, a, b, A, B, s) for(auto&& [i, a, b]: ENUMZIP(A, B, s)) #define overload6(a, b, c, d, e, f, g, ...) g #define zip(...) overload6(__VA_ARGS__, enumzip6, enumzip5, zip4, _, _, _)(__VA_ARGS__) vector<char> stoc(string &S){ int n = S.size(); vector<char> ret(n); for(int i = 0; i < n; i++) ret[i] = S[i]; return ret; } #define INT(...) int __VA_ARGS__; inp(__VA_ARGS__); #define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__); #define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__); #define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__); #define VEC(T, A, n) vector<T> A(n); inp(A); #define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A); const ll MOD1 = 1000000007; const ll MOD9 = 998244353; template<class T> auto min(const T& a){ return *min_element(all(a)); } template<class T> auto max(const T& a){ return *max_element(all(a)); } template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } void FLUSH(){cout << flush;} void print(){cout << endl;} template <class Head, class... Tail> void print(Head &&head, Tail &&... tail) { cout << head; if (sizeof...(Tail)) cout << spa; print(forward<Tail>(tail)...); } template<typename T> void print(vector<T> &A){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << endl; else cout << spa; } } template<typename T> void print(vector<vector<T>> &A){ for(auto &row: A) print(row); } template<typename T, typename S> void print(pair<T, S> &A){ cout << A.first << spa << A.second << endl; } template<typename T, typename S> void print(vector<pair<T, S>> &A){ for(auto &row: A) print(row); } template<typename T, typename S> void prisep(vector<T> &A, S sep){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << endl; else cout << sep; } } template<typename T, typename S> void priend(T A, S end){ cout << A << end; } template<typename T> void priend(T A){ priend(A, spa); } template<class... T> void inp(T&... a){ (cin >> ... >> a); } template<typename T> void inp(vector<T> &A){ for(auto &a:A) cin >> a; } template<typename T> void inp(vector<vector<T>> &A){ for(auto &row:A) inp(row); } template<typename T, typename S> void inp(pair<T, S> &A){ inp(A.first, A.second); } template<typename T, typename S> void inp(vector<pair<T, S>> &A){ for(auto &row: A) inp(row.first, row.second); } template<typename T> T sum(vector<T> &A){ T tot = 0; for(auto a:A) tot += a; return tot; } template<typename T> pair<vector<T>, map<T, int>> compression(vector<T> X){ sort(all(X)); X.erase(unique(all(X)), X.end()); map<T, int> mp; for(int i = 0; i < X.size(); i++) mp[X[i]] = i; return {X, mp}; } #line 2 "Library/C++/data_structure/SWAG.hpp" template<class S, S(*op)(S, S), S(*e)()> struct SWAG{ vector<S> L, R, Lcum; S Rall; SWAG(){ Lcum = {e()}; Rall = e(); } void push(S x){ R.push_back(x); Rall = op(Rall, x); } void pop(){ if(L.empty()){ assert(!R.empty()); while(!R.empty()){ S x = R.back(); R.pop_back(); L.push_back(x); Lcum.push_back(op(x, Lcum[Lcum.size() - 1])); } Rall = e(); } L.pop_back(); Lcum.pop_back(); } S prod(){ return op(Lcum[Lcum.size() - 1], Rall); } int size(){ return L.size() + R.size(); } void clear(){ L.clear(); R.clear(); Lcum = {e()}; Rall = e(); } }; #line 2 "Library/C++/other/Modint.hpp" template<int MOD> struct Modint{ int x; Modint() : x(0){} Modint(int64_t y){ if(y >= 0) x = y % MOD; else x = (y % MOD + MOD) % MOD; } Modint &operator+=(const Modint &p){ x += p.x; if(x >= MOD) x -= MOD; return *this; } Modint &operator-=(const Modint &p){ x -= p.x; if(x < 0) x += MOD; return *this; } Modint &operator*=(const Modint &p){ x = int(1LL * x * p.x % MOD); return *this; } Modint &operator/=(const Modint &p){ *this *= p.inverse(); return *this; } Modint &operator%=(const Modint &p){ assert(p.x == 0); return *this; } Modint operator-() const{ return Modint(-x); } Modint& operator++() { x++; if (x == MOD) x = 0; return *this; } Modint& operator--() { if (x == 0) x = MOD; x--; return *this; } Modint operator++(int) { Modint result = *this; ++*this; return result; } Modint operator--(int) { Modint result = *this; --*this; return result; } friend Modint operator+(const Modint &lhs, const Modint &rhs){ return Modint(lhs) += rhs; } friend Modint operator-(const Modint &lhs, const Modint &rhs){ return Modint(lhs) -= rhs; } friend Modint operator*(const Modint &lhs, const Modint &rhs){ return Modint(lhs) *= rhs; } friend Modint operator/(const Modint &lhs, const Modint &rhs){ return Modint(lhs) /= rhs; } friend Modint operator%(const Modint &lhs, const Modint &rhs){ assert(rhs.x == 0); return Modint(lhs); } bool operator==(const Modint &p) const{ return x == p.x; } bool operator!=(const Modint &p) const{ return x != p.x; } bool operator<(const Modint &rhs) { return x < rhs.x; } bool operator<=(const Modint &rhs) { return x <= rhs.x; } bool operator>(const Modint &rhs) { return x > rhs.x; } bool operator>=(const Modint &rhs) { return x >= rhs.x; } Modint inverse() const{ int a = x, b = MOD, u = 1, v = 0, t; while(b > 0){ t = a / b; a -= t * b; u -= t * v; swap(a, b); swap(u, v); } return Modint(u); } Modint pow(int64_t k) const{ Modint ret(1); Modint y(x); while(k > 0){ if(k & 1) ret *= y; y *= y; k >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const Modint &p){ return os << p.x; } friend istream &operator>>(istream &is, Modint &p){ int64_t y; is >> y; p = Modint<MOD>(y); return (is); } static int get_mod(){ return MOD; } }; struct Arbitrary_Modint{ int x; static int MOD; static void set_mod(int mod){ MOD = mod; } Arbitrary_Modint() : x(0){} Arbitrary_Modint(int64_t y){ if(y >= 0) x = y % MOD; else x = (y % MOD + MOD) % MOD; } Arbitrary_Modint &operator+=(const Arbitrary_Modint &p){ x += p.x; if(x >= MOD) x -= MOD; return *this; } Arbitrary_Modint &operator-=(const Arbitrary_Modint &p){ x -= p.x; if(x < 0) x += MOD; return *this; } Arbitrary_Modint &operator*=(const Arbitrary_Modint &p){ x = int(1LL * x * p.x % MOD); return *this; } Arbitrary_Modint &operator/=(const Arbitrary_Modint &p){ *this *= p.inverse(); return *this; } Arbitrary_Modint &operator%=(const Arbitrary_Modint &p){ assert(p.x == 0); return *this; } Arbitrary_Modint operator-() const{ return Arbitrary_Modint(-x); } Arbitrary_Modint& operator++() { x++; if (x == MOD) x = 0; return *this; } Arbitrary_Modint& operator--() { if (x == 0) x = MOD; x--; return *this; } Arbitrary_Modint operator++(int) { Arbitrary_Modint result = *this; ++*this; return result; } Arbitrary_Modint operator--(int) { Arbitrary_Modint result = *this; --*this; return result; } friend Arbitrary_Modint operator+(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){ return Arbitrary_Modint(lhs) += rhs; } friend Arbitrary_Modint operator-(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){ return Arbitrary_Modint(lhs) -= rhs; } friend Arbitrary_Modint operator*(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){ return Arbitrary_Modint(lhs) *= rhs; } friend Arbitrary_Modint operator/(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){ return Arbitrary_Modint(lhs) /= rhs; } friend Arbitrary_Modint operator%(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){ assert(rhs.x == 0); return Arbitrary_Modint(lhs); } bool operator==(const Arbitrary_Modint &p) const{ return x == p.x; } bool operator!=(const Arbitrary_Modint &p) const{ return x != p.x; } bool operator<(const Arbitrary_Modint &rhs) { return x < rhs.x; } bool operator<=(const Arbitrary_Modint &rhs) { return x <= rhs.x; } bool operator>(const Arbitrary_Modint &rhs) { return x > rhs.x; } bool operator>=(const Arbitrary_Modint &rhs) { return x >= rhs.x; } Arbitrary_Modint inverse() const{ int a = x, b = MOD, u = 1, v = 0, t; while(b > 0){ t = a / b; a -= t * b; u -= t * v; swap(a, b); swap(u, v); } return Arbitrary_Modint(u); } Arbitrary_Modint pow(int64_t k) const{ Arbitrary_Modint ret(1); Arbitrary_Modint y(x); while(k > 0){ if(k & 1) ret *= y; y *= y; k >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const Arbitrary_Modint &p){ return os << p.x; } friend istream &operator>>(istream &is, Arbitrary_Modint &p){ int64_t y; is >> y; p = Arbitrary_Modint(y); return (is); } static int get_mod(){ return MOD; } }; int Arbitrary_Modint::MOD = 998244353; using modint9 = Modint<998244353>; using modint1 = Modint<1000000007>; using modint = Arbitrary_Modint; #line 2 "Library/C++/math/modpow.hpp" template<typename T> T modpow(T a, long long b, T MOD){ T ret = 1; while(b > 0){ if(b & 1){ ret *= a; ret %= MOD; } a *= a; a %= MOD; b >>= 1; } return ret; } #line 3 "Library/C++/convolution/convolution.hpp" namespace FFT{ using ll = long long; const ll MOD = 998244353; const int g = 3; template<typename T> void butterfly(vector<T> &a) { int n = a.size(); int h = 0; while((1 << h) < n) h++; static bool first = true; static T sum_e[30]; if(first) { first = false; T es[30], ies[30]; int cnt2 = __builtin_ctz(MOD - 1); T e = modpow<T>(g, (MOD - 1) >> cnt2, MOD); T ie = modpow<T>(e, MOD - 2, MOD); for(int i = cnt2; i >= 2; i--){ es[i - 2] = e; ies[i - 2] = ie; e *= e; e %= MOD; ie *= ie; ie %= MOD; } T now = 1; for(int i = 0; i < cnt2 - 2; i++){ sum_e[i] = es[i] * now % MOD; now *= ies[i]; now %= MOD; } } for(int ph = 1; ph <= h; ph++){ int w = 1 << (ph - 1); int p = 1 << (h - ph); T now = 1; for(int s = 0; s < w; s++){ int offset = s << (h - ph + 1); for(int i = 0; i < p; i++){ auto l = a[i + offset]; auto r = a[i + offset + p] * now % MOD; a[i + offset] = (l + r) % MOD; a[i + offset + p] = (l - r) % MOD; } now *= sum_e[__builtin_ctz(~(unsigned int)(s))]; now %= MOD; } } } template<typename T> void butterfly_inv(vector<T> &a) { int n = a.size(); int h = 1; while((1 << h) < n) h++; static bool first = true; static T sum_ie[30]; if(first) { first = false; T es[30], ies[30]; int cnt2 = __builtin_ctz(MOD - 1); T e = modpow<T>(g, (MOD - 1) >> cnt2, MOD); T ie = modpow<T>(e, MOD - 2, MOD); for(int i = cnt2; i >= 2; i--){ es[i - 2] = e; ies[i - 2] = ie; e *= e; e %= MOD; ie *= ie; ie %= MOD; } T now = 1; for(int i = 0; i < cnt2 - 2; i++){ sum_ie[i] = ies[i] * now % MOD; now *= es[i]; now %= MOD; } } for(int ph = h; ph > 0; ph--){ int w = 1 << (ph - 1); int p = 1 << (h - ph); T inow = 1; for(int s = 0; s < w; s++){ int offset = s << (h - ph + 1); for(int i = 0; i < p; i++){ auto l = a[i + offset]; auto r = a[i + offset + p]; a[i + offset] = (l + r) % MOD; a[i + offset + p] = (l - r) * inow % MOD; } inow *= sum_ie[ __builtin_ctz(~(unsigned int)(s))]; inow %= MOD; } } } template<typename T> vector<T> convolution(vector<T> a, vector<T> b){ int n = a.size(); int m = b.size(); if(min(n, m) <= 60){ if(n < m){ swap(n, m); swap(a, b); } vector<T> ans(n + m - 1); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ ans[i + j] += a[i] * b[j]; ans[i + j] %= MOD; } } for(int i = 0; i < n + m - 1; i++){ if(ans[i] < 0) ans [i] += MOD; } return ans; } int z = 1; while(z < n + m - 1) z *= 2; a.resize(z); butterfly(a); b.resize(z); butterfly(b); for(int i = 0; i < z; i++){ a[i] *= b[i]; a[i] %= MOD; } butterfly_inv(a); a.resize(n + m - 1); T iz = modpow<T>(z, MOD - 2, MOD); for(int i = 0; i < n + m - 1; i++){ a[i] *= iz; a[i] = (a[i] % MOD + MOD) % MOD; } return a; } }; #line 188 "A.cpp" using mint = modint9; int n, m, k; struct S{ vector<mint> A; }; S e(){ S ret; ret.A.assign(k, 0); ret.A[0] = 1; return ret; } S op(S l, S r){ auto B = FFT::convolution(l.A, r.A); fori(i, k, B.size()){ B[i - k] += B[i]; } B.resize(k); S ret; ret.A = B; return ret; } void solve(){ inp(n, m, k); VEC(ll, A, n); SWAG<S, op, e> swag; fori(i, m){ S B = e(); B.A[A[i]] += 1; swag.push(B); } print(swag.prod().A[0] - 1); fori(i, m, n){ S B = e(); B.A[A[i]] += 1; swag.push(B); swag.pop(); print(swag.prod().A[0] - 1); } } int main(){ cin.tie(0)->sync_with_stdio(0); // cout << fixed << setprecision(12); int t; t = 1; // cin >> t; while(t--) solve(); return 0; }