Submission #3027280

---

Source Code Expand

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <iomanip>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
const int inf = 1e9;
const ll linf = 1LL << 50;
const int mod = 1e9+7;

int n, m;
map<int, int> mpa;
map<int, int> mpb;
vector<int> veca;
vector<int> vecb;

ll dp[1001][101];
ll ans[101][1001];
ll ansb[101][1001];
int suma = 0;
int sumb = 0;

int main(int argc, char const* argv[])
{
	cin >> n >> m;
	for(int i = 0; i < n; i++){
			int x;
			cin >> x;
			mpa[x]++;
			if(i == 0 || veca[veca.size() - 1] != x)veca.pb(x);
			sumb += x;
	}
	for(int i = 0; i < m; i++){
			int x;
			cin >> x;
			mpb[x]++;
			if(i == 0 || vecb[vecb.size() - 1] != x)vecb.pb(x);
			suma += x;
	}
	for(int i = 0; i <= 100; i++){
			dp[0][i] = 1;
	}
	for(int i = 1; i <= 1000; i++){
			for(int j = 1; j <= 100; j++){
					dp[i][j] = dp[i][j-1];
					if(i >= j)dp[i][j] += dp[i-j][j];
					dp[i][j] %= mod;
			}
	}
	ans[0][0] = 1;
	for(int i = 0; i < veca.size(); i++){
			ans[i+1][0] = 1;
			for(int j = 1; j <= suma; j++){
					ans[i+1][j] = 0;
					for(int k = 0; k <= j; k++){
							ans[i+1][j] += ans[i][j-k] * dp[k][mpa[veca[i]]] % mod;
							ans[i+1][j] %= mod;
					}
			}
	}
	ansb[0][0] = 1;
	for(int i = 0; i < vecb.size(); i++){
			ansb[i+1][0] = 1;
			for(int j = 1; j <= sumb; j++){
					ansb[i+1][j] = 0;
					for(int k = 0; k <= j; k++){
							ansb[i+1][j] += ansb[i][j-k] * dp[k][mpb[vecb[i]]] % mod;
							ansb[i+1][j] %= mod;
					}
			}
	}
	cout << ans[veca.size()][suma] * ansb[vecb.size()][sumb] % mod << endl;
	return 0;
}

Submission Info

Judge Result