結果
問題 |
No.1304 あなたは基本が何か知っていますか?私は知っています.
|
ユーザー |
![]() |
提出日時 | 2020-12-02 00:27:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 1,644 bytes |
コンパイル時間 | 1,837 ms |
コンパイル使用メモリ | 171,264 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2025-06-22 02:49:59 |
合計ジャッジ時間 | 10,885 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 44 WA * 9 RE * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; void dfs(vector<vector<long long>> &H, vector<int> &A, int r, int prv, int x){ if (r == 0){ H[prv][x]++; } else { int K = A.size(); for (int j = 0; j < K; j++){ if (A[j] != prv){ dfs(H, A, r - 1, A[j], x ^ A[j]); } } } } vector<long long> fwt(vector<long long> A, int N, bool inv){ for (int i = 0; i < N; i++){ for (int j = 0; j < (1 << N); j++){ if (!(j >> i & 1)){ long long x = A[j]; long long y = A[j | (1 << i)]; A[j] = x + y; A[j | (1 << i)] = x - y; if (inv){ A[j] /= 2; A[j | (1 << i)] /= 2; } } } } return A; } vector<long long> xor_convolution(vector<long long> A, vector<long long> B, int N){ A = fwt(A, N, false); B = fwt(B, N, false); vector<long long> C(1 << N); for (int i = 0; i < (1 << N); i++){ C[i] = A[i] * B[i]; } C = fwt(C, N, true); return C; } int main(){ int N, K, X, Y; cin >> N >> K >> X >> Y; Y = min(Y, 1023); vector<int> A(K); for (int i = 0; i < K; i++){ cin >> A[i]; } vector<vector<long long>> H(1024, vector<long long>(1024, 0)); dfs(H, A, N / 2, -1, 0); vector<long long> sum(1024, 0); for (int i = 0; i < 1024; i++){ for (int j = 0; j < 1024; j++){ sum[j] += H[i][j]; } } sum = xor_convolution(sum, sum, 10); long long ans = 0; for (int i = X; i <= Y; i++){ ans += sum[i]; } ans %= MOD; for (int i = 0; i < 1024; i++){ H[i] = xor_convolution(H[i], H[i], 10); for (int j = X; j <= Y; j++){ ans += MOD - H[i][j]; } ans %= MOD; } cout << ans << endl; }