题解

#include<bits/stdc++.h>
#include<assert.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pir;
const int M = 105;
const int N = 35;
const int mod = 998244353;
ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
void add(ll &x, ll y) {
    x += y;
    x %= mod;
}
ll v[M];
int n, m, k, Extra;
namespace Q1 {
//dp[i][s]:到了第 i 个数，且状态为 s 的方案数总和
ll dp[N][1 << 17];

// 对于状态 sta 上的 val 位 +1
ll update(ll sta , ll val) {
    for (int i = val; i <= m + Extra; i++) {
        if ((1ll << i)&sta) {
            sta -= 1ll << i;
        } else {
            sta += 1ll << i;
            break;
        }
    }
    return sta;
}
void solve() {
    Extra = log2(n) + 1;
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int sta = 0; sta <= 1 << (m + Extra); sta++) {
            if (dp[i][sta] == 0)continue;
            // 考虑第 i+1 数选 v[j];
            for (int j = 0; j <= m; j++) {
                int now_sta = update(sta, j);
                // cout << sta << " " << j << " " << now_sta << '\n';
                add(dp[i + 1][now_sta], dp[i][sta] * v[j] % mod);
            }
        }
    }
    int z = 0;
    ll ans = 0;
    for (int sta = 0; sta <= 1 << (m + Extra); sta++) {
        int cnt = 0;
        for (int j = 0; j <= (m + Extra); j++) {
            if ((1 << j)&sta) {
                cnt++;
            }
        }
        if (cnt > k)continue;
        // cout << (z++) - 1 << " " << dp[n][sta] << '\n';
        add(ans, dp[n][sta]);
    }
    cout << ans << '\n';
}
}
namespace Q2 {
__int128 p[M + 11];
ll fac[N], inv_fac[N], a[N];
ll ans;
__int128 tot;
void dfs(int deep, int maxx, __int128 have) {
    if (have < 0)return;
    if (deep == n + 1) {
        have = tot - have;
        int now = 0;
        for (int i = 0; i <= m + Extra; i++) {
            if (p[i]&have) {
                now++;
            }
        }
        if (now > k)return;
        ll res = 1;
        for (int i = 1; i <= n; i++) {
            res = (res * v[a[i]] % mod) % mod;
        }
        ll cnt = fac[n];
        for (int i = 1; i <= n; i++) {
            int j = i;
            while (j + 1 <= n && a[j + 1] == a[i])j++;
            cnt = cnt * inv_fac[j - i + 1] % mod;
            i = j;
        }
        add(ans, res * cnt % mod);
        return;
    }
    for (int i = maxx; i >= 0; i--) {
        a[deep] = i;
        dfs(deep + 1, i, have - p[i]);
    }
}
void solve() {
    p[0] = 1;
    Extra = log2(n) + 1;
    for (int i = 1; i <= 110; i++)p[i] = p[i - 1] * 2;
    fac[0] = 1;
    for (int i = 1; i <= 30; i++)fac[i] = fac[i - 1] * i % mod;
    for (int i = 0; i <= 30; i++)inv_fac[i] = qpow(fac[i], mod - 2);
    ans = 0;
    tot = p[m + Extra];

    dfs(1, m, tot);
    cout << ans << '\n';
}
}

namespace Q3 {
ll ans;
// dp[i][j][k]:到了第 i 位用了 j 次操作，当前位有 k 个的方案数
ll dp[M + 10][N][N];
ll fac[N], inv_fac[N];
void solve() {
    fac[0] = 1;
    for (int i = 1; i <= 30; i++) {
        fac[i] = (fac[i - 1] * i) % mod;
    }
    for (int i = 0; i <= 30; i++) {
        inv_fac[i] = qpow(fac[i], mod - 2);
    }
    Extra = log2(n) + 1;
    ans = 0;
    // 一次没操作的方案数是 1
    for (int i = 0; i <= m; i++) {
        dp[i][0][0] = 1;
    }
    for (int i = 0; i <= m + Extra - 1; i++) {
        for (int j = 0; j <= n; j++) {
            for (int op = 0; op <= n; op++) {
                auto tot = dp[i][j][op];
                if (tot == 0)continue;
                // 考虑当前 拿 k 个;
                for (int k = 0; k <= n - j; k++) {
                    // 如果当前留下奇数，则转移是不合法的
                    if ((op + k) % 2)continue;
                    if (op + k == 0)continue;
                    ll val = (tot * qpow(v[i], k)) % mod;
                    val = (val * inv_fac[k]) % mod;
                    add(dp[i + 1][j + k][(op + k) / 2], val);
                }
            }
        }
    }
    for (int i = 0; i <= m + Extra; i++) {
        // cout << i << " " << dp[i][n][1] << " " << dp[i][n - 1][0]*v[i] % mod << '\n';
        add(ans, dp[i][n][1]);
    }
    cout << ans*fac[n] % mod << '\n';
}
}

namespace Q4 {
ll ans;
// dp[i][j][k][f]:到了第 i 位用了 j 次操作，当前位有 k 个的方案数，且前面 1 的个数为 f 的方案数
ll dp[M + 10][N][N][N];
ll fac[N], inv_fac[N];
void solve() {
    fac[0] = 1;
    for (int i = 1; i <= 30; i++) fac[i] = (fac[i - 1] * i) % mod;
    for (int i = 0; i <= 30; i++) inv_fac[i] = qpow(fac[i], mod - 2);
    Extra = log2(n) + 1;
    ans = 0;
    // 一次没操作的方案数是 1
    // dp[0][1][1][0] = v[0];
    for (int i = 0; i <= m; i++) {
        dp[i][0][0][0] = 1;
    }
    for (int i = 0; i <= m + Extra; i++) {
        for (int j = 0; j <= n; j++) {
            for (int op = 0; op <= n; op++) {
                for (int f = 0; f <= k; f++) {
                    auto tot = dp[i][j][op][f];
                    if (tot == 0)continue;
                    // if (i <= m) {
                    // 考虑当前 拿 g 个;
                    for (int g = 0; g <= n - j; g++) {
                        if (op + g == 0 && f == 0)continue;
                        if ((op + g) % 2 == 0) {
                            ll val = (tot * qpow(v[i], g)) % mod;
                            val = (val * inv_fac[g]) % mod;
                            add(dp[i + 1][j + g][(op + g) / 2][f], val);
                        } else {
                            ll val = (tot * qpow(v[i], g)) % mod;
                            val = (val * inv_fac[g]) % mod;
                            add(dp[i + 1][j + g][(op + g) / 2][f + 1], val);
                        }
                    }

                }
            }
        }
    }
    // cout << dp[1][1][0][1] << '\n';
    // cout << dp[2][1][0][1] << '\n';
    // for (int i = 0; i <= m + Extra + 1; i++) {
    //     for (int f = 0; f <= k; f++) {
    //         cout << i << " " << f << " " << dp[i][n][0][f]*fac[n] % mod << '\n';
    //     }
    // }
    for (int f = 0; f <= k; f++) {
        add(ans, dp[m + Extra + 1][n][0][f]);
    }
    cout << ans*fac[n] % mod << '\n';
}
}
void solve() {
    cin >> n >> m >> k;
    for (int i = 0; i <= m; i++)cin >> v[i];
    // Q4::solve();
    // Q1::solve();
    if (m <= 12) {
        Q1::solve();
    }
    else if (n <= 5) {
        Q2::solve();
    } else if (k == 1) {
        Q3::solve();
    } else {
        Q4::solve();
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    solve();
}
/*
考虑 k=1 时的方案数
9+4+1
*/