三金.紫题题解

点击查看代码

</details>\#include <bits/stdc++.h>using namespace std;
using ll = long long;const int MOD = 998244353;
const int G = 3;// 快速幂
ll qpow(ll b, ll e) {ll res = 1;b %= MOD;while (e > 0) {if (e & 1) res = res * b % MOD;b = b * b % MOD;e >>= 1;}return res;
}// 数论变换 (NTT)
void ntt(vector<ll>& a, int type) {int n = a.size();vector<int> rev(n);for (int i = 0; i < n; i++) {rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);if (i < rev[i]) swap(a[i], a[rev[i]]);}for (int mid = 1; mid < n; mid <<= 1) {ll wn = qpow(G, (MOD - 1) / (mid << 1));if (type == -1) wn = qpow(wn, MOD - 2);for (int i = 0; i < n; i += (mid << 1)) {ll w = 1;for (int j = 0; j < mid; j++, w = w * wn % MOD) {ll x = a[i + j], y = w * a[i + j + mid] % MOD;a[i + j] = (x + y) % MOD;a[i + j + mid] = (x - y + MOD) % MOD;}}}if (type == -1) {ll inv = qpow(n, MOD - 2);for (int i = 0; i < n; i++) a[i] = a[i] * inv % MOD;}
}// 多项式乘法
vector<ll> mul(vector<ll> a, vector<ll> b) {int deg = a.size() + b.size() - 1;int len = 1;while (len < deg) len <<= 1;a.resize(len);b.resize(len);ntt(a, 1);ntt(b, 1);for (int i = 0; i < len; i++) {a[i] = a[i] * b[i] % MOD;}ntt(a, -1);a.resize(deg);return a;
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, k;cin >> n >> k;int m = n / 2;vector<ll> p(10, 0);for (int i = 0; i < k; ++i) {int d;cin >> d;p[d] = 1;}vector<ll> res = {1}; // 初始为 P(x)^0 = 1// 多项式快速幂while (m > 0) {if (m & 1) res = mul(res, p);p = mul(p, p);m >>= 1;}ll ans = 0;for (ll c : res) {ans = (ans + c * c % MOD) % MOD;}cout << ans << endl;return 0;
}