結果
問題 |
No.1304 あなたは基本が何か知っていますか?私は知っています.
|
ユーザー |
![]() |
提出日時 | 2020-12-02 13:43:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 2,571 bytes |
コンパイル時間 | 1,824 ms |
コンパイル使用メモリ | 204,356 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-22 02:55:50 |
合計ジャッジ時間 | 5,767 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 WA * 19 RE * 10 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define all(hoge) (hoge).begin(), (hoge).end() #define en '\n' using ll = long long; using ull = unsigned long long; #define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i) #define rep2(i, m, n) for(ll i = (ll)(n)-1; i >= (ll)(m); --i) #define REP(i, n) rep(i, 0, n) #define REP2(i, n) rep2(i, 0, n) template<class T> using vec = vector<T>; template<class T> using vvec = vector<vec<T>>; typedef pair<ll, ll> P; using tp = tuple<ll, ll, ll>; constexpr long long INF = 1LL << 60; constexpr int INF_INT = 1 << 25; //constexpr long long MOD = (ll) 1e9 + 7; constexpr long long MOD = 998244353LL; using ld = long double; static const ld pi = 3.141592653589793L; using Array = vector<ll>; using Matrix = vector<Array>; /* #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") */ template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } void solve() { ll n, k, x, y; cin >> n >> k >> x >> y; vec<ll> a(k); REP(i, k) { cin >> a[i]; } //重複を取り除く sort(all(a)); auto result = unique(all(a)); a.erase(result, a.end()); vvec<ll> dp(n + 1, vec<ll>(1024, -1)); auto dfs = [&](auto &&self, ll i, ll j) -> ll { if (dp[i][j] !=-1) return dp[i][j]; if (i == 0) return dp[i][j] = j==0; if (i == 1) { ll ret = 0; REP(l, a.size()) { ret += self(self, i - 1, (j ^ a[l])); } return dp[i][j] = ret; } //2連続でa[l]をつかうと同じ合計xorになるので、除く。 if (i == 2) { ll ret = 0; REP(l, a.size()) { ret += self(self, i - 1, (j ^ a[l])); } ret -= self(self, i - 2, j) * k; return dp[i][j] = ret; } ll ret = 0; REP(l, a.size()) { ret += self(self, i - 1, (j ^ a[l])); } ret -= self(self, i - 2, j) * (k - 1); return dp[i][j] = ret; }; ll ans = 0; chmin(y, 1023LL); rep(i, x, y + 1) { ans += dfs(dfs, n, i); ans %= MOD; } cout << ans << en; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); /* ll t; cin >> t; REP(i, t - 1) { solve(); }*/ solve(); return 0; }