C++(g++ 7.5.0) 解法, 执行用时: 305ms, 内存消耗: 66196K, 提交时间: 2022-08-24 20:22:38

#include<bits/stdc++.h>
using namespace std ;
const int N = 12 ;
const int mod = 998244353 ;
#define ll long long
int n,stp ;
int f[1<<N][1<<N] ;
int x[N],fac[1<<N],op[N][1<<N] ;
int jc[1<<N],inv[1<<N] ;
int qsm(int a,int b)
{
    int ans=1 ;
    while(b)
    {
        if(b&1) ans=(ll)ans*a%mod ;
        a=(ll)a*a%mod ; b>>=1 ;
    }
    return ans ;
}
int C(int n,int m)
{
    if(n<m) return 0 ;
    if(m<0) return 0 ;
    return (ll)jc[n]*inv[m]%mod*inv[n-m]%mod ;
}
int main()
{
    cin>>n>>stp ;
    for(int i=0;i<n;++i) cin>>x[i],x[i]++ ;
    fac[0]=1 ; jc[0]=1 ;
    for(int i=1;i<=stp;++i) fac[i]=(fac[i-1]<<1)%mod,jc[i]=(ll)jc[i-1]*i%mod ;
    fac[stp]=qsm(fac[stp],mod-2) ;
    inv[stp]=qsm(jc[stp],mod-2) ;
    for(int i=stp;i>=1;--i) inv[i-1]=(ll)inv[i]*i%mod ;
    for(int i=1;i<(1<<n);++i)
        for(int j=0;j<n;j++) if(i>>j&1)
        {
            int res=0 ;
            for(int k=j+1;k<n;++k)
                if(i>>k&1) res++ ;
            op[j][i]=(res&1)?(mod-1):1 ;
        }
    memset(f,0,sizeof(f)) ;
    f[0][0]=1 ;
    for(int j=1;j<=x[n-1]+stp;j++)
        for(int i=0;i<(1<<n);++i)
        {
            f[i][j]=f[i][j-1] ;
            for(int k=0;k<n;++k) if(i>>k&1)
                f[i][j]=(f[i][j]+(ll)op[k][i]*f[i^(1<<k)][j-1]%mod*C(stp,j-x[k])%mod*fac[stp]%mod)%mod ;
           // printf("f[%d][%d]=%d\n",i,j,f[i][j]) ;
        }
    cout<<f[(1<<n)-1][x[n-1]+stp]<<'\n' ;
    return 0 ;
}

C++(clang++ 11.0.1) 解法, 执行用时: 159ms, 内存消耗: 39200K, 提交时间: 2022-09-07 18:14:40

#include<bits/stdc++.h>
const int mod = 998244353;
typedef long long ll;
ll dp[1 << 10][2005], c[2005][2005], inv;
using namespace std;
ll qmi(ll m, ll k, ll p)
{
    ll res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
ll C(ll a, ll b){
    if(b < 0 || b > a) return 0;
    return c[a][b];
}
int main(){
    for (int i = 0; i <= 2000; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    
    inv = qmi(2, mod - 2, mod);
    ll k, n, x[15], ans = 0;
    cin >> k >> n;
    for(int i = 1; i <= k; i ++) {cin >> x[i];x[i] ++;}
    for(int j = 0; j <= 2001; j ++) dp[0][j] = 1;
    
     for(int i = 1; i < (1 << k) ; i ++)
        for(int j = 1; j <= 2001; j ++) {
            ll cnt = 1;
            dp[i][j] = dp[i][j - 1];
            for(int p = k - 1; p >= 0; p --){
                if(i >> p & 1) {
                dp[i][j] = (dp[i][j] + cnt * dp[i - (1 << p)][j - 1] % mod * C(n, j - x[p + 1]) % mod) % mod;
                cnt = mod - cnt; 
                }
                }
        }
    cout << dp[(1 << k) - 1][2001] * qmi(inv, n * k, mod) % mod;
}