Submission #3419882

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
ll powmod(ll a, ll k){
    ll ap=a, ans=1;
    while(k>0){
        if(k%2==1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k/=2;
    }
    return ans;
}
ll inv(ll a){
	return powmod(a, MOD-2);
}

int main()
{
	int n; ll d;
	cin>>n>>d;
	ll f[901];
	f[0]=1;
	for(ll i=1; i<=900; i++){
		f[i]=f[i-1]*i%MOD;
	}
	ll invf[901];
	invf[900]=inv(f[900]);
	for(ll i=899; i>=0; i--) invf[i]=invf[i+1]*(i+1)%MOD;

	int a[31];
	int asum=0;
	for(int i=1; i<=n; i++){
		cin>>a[i];
		asum+=(a[i]-1);
	}
	ll dp[31][31][901]={};
	dp[0][0][0]=1;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=i; j++){
			for(int k=0; k<=asum; k++){
				dp[i][j][k]=dp[i-1][j][k];
				for(int l=0; l<a[i]; l++){
					if(k>=l) dp[i][j][k]+=(dp[i-1][j-1][k-l]*f[k]%MOD*invf[k-l]%MOD*invf[l]%MOD);
				}
				dp[i][j][k]%=MOD;
			}
		}
	}
	ll fd[901];
	fd[0]=1, fd[1]=d;
	ll prod=d;
	for(ll i=2; i<=asum; i++){
		prod=prod*(d-i+1)%MOD;
		fd[i]=prod*invf[i]%MOD;
	}
	ll ans=powmod((ll)n, d);
	for(int i=1; i<=n; i++){
		for(int j=0; j<=asum; j++){
			if(d<j) continue;
			if(i%2){
				ans-=(fd[j]*dp[n][i][j]%MOD*powmod((ll)(n-i), d-(ll)j)%MOD);
				ans+=MOD;
			}else{
				ans+=(fd[j]*dp[n][i][j]%MOD*powmod((ll)(n-i), d-(ll)j)%MOD);
			}
			ans%=MOD;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result