Submission #71705431

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int G = 3;  // 998244353的原根

// 快速幂
int modpow(int a, long long b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
        b >>= 1;
    }
    return res;
}

// NTT 核心函数
void ntt(vector<int>& a, bool invert) {
    int n = (int)a.size();
    
    // 位逆序置换
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    
    for (int len = 2; len <= n; len <<= 1) {
        int wlen = modpow(G, (MOD - 1) / len);
        if (invert) wlen = modpow(wlen, MOD - 2);
        
        for (int i = 0; i < n; i += len) {
            int w = 1;
            for (int j = 0; j < len / 2; j++) {
                int u = a[i + j];
                int v = 1LL * a[i + j + len / 2] * w % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                w = 1LL * w * wlen % MOD;
            }
        }
    }
    
    if (invert) {
        int inv_n = modpow(n, MOD - 2);
        for (int& x : a) x = 1LL * x * inv_n % MOD;
    }
}

// 多项式乘法
vector<int> multiply(vector<int> a, vector<int> b) {
    int n = 1;
    int need = (int)a.size() + (int)b.size() - 1;
    while (n < need) n <<= 1;
    
    a.resize(n);
    b.resize(n);
    
    ntt(a, false);
    ntt(b, false);
    
    for (int i = 0; i < n; i++) {
        a[i] = 1LL * a[i] * b[i] % MOD;
    }
    
    ntt(a, true);
    a.resize(need);
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    long long M;
    cin >> N >> M;
    
    vector<int> A(N);
    int sumA = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sumA += A[i];
    }
    
    // 计算多项式 Q(z) = (1-z) * ∏(1 - z^{A_i})
    // 使用动态规划计算
    int D = sumA + 1;
    vector<int> Q(D + 1, 0);
    Q[0] = 1;
    Q[1] = MOD - 1;  // -1 mod MOD
    
    for (int a : A) {
        for (int k = D; k >= a; k--) {
            Q[k] = (Q[k] - Q[k - a]) % MOD;
            if (Q[k] < 0) Q[k] += MOD;
        }
    }
    
    // 修剪 Q 的长度，去掉高位的零
    while (Q.size() > 1 && Q.back() == 0) Q.pop_back();
    
    // Bostan-Mori 算法
    vector<int> P = {1};  // P(z) = 1
    long long n = M;
    
    while (n > 0) {
        // 计算 Q_minus(z) = Q(-z)
        vector<int> Q_minus(Q.size());
        for (size_t i = 0; i < Q.size(); i++) {
            if (i % 2 == 0) {
                Q_minus[i] = Q[i];
            } else {
                Q_minus[i] = (MOD - Q[i]) % MOD;
            }
        }
        
        // 计算 U(z) = P(z) * Q_minus(z)
        vector<int> U = multiply(P, Q_minus);
        
        // 计算新的 P(z)
        vector<int> P_new;
        if (n % 2 == 0) {
            // 取偶次项
            P_new.resize((U.size() + 1) / 2);
            for (size_t i = 0; i < P_new.size(); i++) {
                int idx = 2 * i;
                P_new[i] = (idx < U.size()) ? U[idx] : 0;
            }
        } else {
            // 取奇次项
            P_new.resize(U.size() / 2);
            for (size_t i = 0; i < P_new.size(); i++) {
                int idx = 2 * i + 1;
                P_new[i] = (idx < U.size()) ? U[idx] : 0;
            }
        }
        
        // 计算 V(z) = Q(z) * Q_minus(z)
        vector<int> V = multiply(Q, Q_minus);
        
        // 计算新的 Q(z)（取偶次项）
        vector<int> Q_new((V.size() + 1) / 2);
        for (size_t i = 0; i < Q_new.size(); i++) {
            int idx = 2 * i;
            Q_new[i] = (idx < V.size()) ? V[idx] : 0;
        }
        
        // 更新
        P = P_new;
        Q = Q_new;
        n /= 2;
    }
    
    // 计算结果：P[0] * inv(Q[0])
    int ans = 1LL * P[0] * modpow(Q[0], MOD - 2) % MOD;
    cout << ans << endl;
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:130:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |                 P_new[i] = (idx < U.size()) ? U[idx] : 0;
      |                             ~~~~^~~~~~~~~~
./Main.cpp:137:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |                 P_new[i] = (idx < U.size()) ? U[idx] : 0;
      |                             ~~~~^~~~~~~~~~
./Main.cpp:148:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |             Q_new[i] = (idx < V.size()) ? V[idx] : 0;
      |                         ~~~~^~~~~~~~~~

Judge Result