Submission #3026467

---

Source Code Expand

#include <bits/stdc++.h>
#define MAX 1000000
#define MOD 1000000007
using namespace std;
typedef long long ll;

int N, M;
map<ll, ll> A, B;
vector<vector<ll>> dp(100001, vector<ll>(101, 0));

ll p(ll n, ll k){
    
    if(k == 0) return !n;
    
    ll& res = dp[n][k];
    if(res) return res;
    
    res += p(n, k - 1);
    res %= MOD;
    res += (n < k) ? 0 : p(n - k, k);
    res %= MOD;
    
    return res;
}

ll solve(ll sum, map<ll, ll> mp){
    
    vector<ll> v(1001, 0);
    vector<ll> w(1001, 0);
    v[sum] = 1;
    
    for(auto m : mp){
        ll x = m.second;
        fill(w.begin(), w.end(), 0);
        
        for(int i = 0; i <= sum; ++i){
            if(v[i]){
                for(int j = 0; j <= i; ++j){
                    (w[i - j] += v[i] * p(j, x)) %= MOD;
                }
            }
        }
        swap(v, w);
    }
    return v[0];
}

int main(void){
    
    cin >> N >> M;
    ll asum = 0, bsum = 0;
    for(int i = 0; i < N; ++i){
        int temp; cin >> temp;
        asum += temp, ++A[temp];
    }
    for(int i = 0; i < M; ++i){
        int temp; cin >> temp;
        bsum += temp, ++B[temp];
    }
    
    ll aans = solve(bsum, A);
    ll bans = solve(asum, B);
    
    cout << (aans * bans) % MOD << endl;
    
    return 0;
}

Submission Info

Judge Result