Submission #1161856

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 1e9+7;
ll dp[500][500];
ll A[500];
ll B[500];
ll powdp[500][500];


ll modPow(ll a, ll b) {
	if (powdp[a][b] > -1) return powdp[a][b];
	ll ret = a;
	if (b == 0) ret = 1;
	if (b > 1) {
		for (ll i = 0; i < b - 1; ++i) {
			if (powdp[a][i+2] > -1) {ret = powdp[a][i+2]; continue;}
			ret *= a;
			ret %= mod;
			powdp[a][i+2] = ret;
		}
	}
	powdp[a][b] = ret;
	return ret;
}

int main() {
	ll N, C;
	cin >> N >> C;
	for (ll i = 0; i < N; ++i) cin >> A[i];
	for (ll i = 0; i < N; ++i) cin >> B[i];
	
	memset(dp, 0, sizeof(dp));
	memset(powdp, -1, sizeof(powdp));
	dp[0][0] =  1;
	for (ll a = 0; a <= N; ++a) {
		for (ll b = 0; b <= C; ++b) {
			ll sum = 0;
			for (ll c = 0; c < b; ++c) sum += dp[a][c] * modPow(A[a], (b - c)); sum %= mod;
			dp[a+1][b] = dp[a][b] + sum;
			dp[a+1][b] %= mod;
		}
	}
	cout << dp[N][C] % mod << endl;
}

Submission Info

Judge Result