E-Union

Problem

atcoder.jp

Solution

・愚直解は、に対し、各個使ってシュミレーションが考えられるが、計算量的に間に合わない。
・配列を次のように定義する
数字を個使ったときの場合の数
・更新は

・更新した値をもう一度更新しないように、後ろから更新していかないと行けない。
・特に、の場合は更新しないこと。
i番目の数字をいくつ使用しても、i-1番目までの計算結果は繰り返し利用できるので、そのあたりに着目するとDPに到達できるかも…？

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
auto dp = vector<vector<int>>(500,vector<int>(3000,0LL));
signed main(){
    int t;
    cin >> t;
    vector<int>v(t);
    for(auto& e : v) cin >> e;
    rep(i,v.size()){ fill(dp[i].begin(),dp[i].begin() + v[i] + 1,1LL);}
    int mod = 1000000007;
    rep(i,dp.size() - 1){
        dp[i][0] = 1;
        if(i == 0)continue;
        for(int j = dp[i].size(); j >= 0;--j){
            if(dp[i][j] == 0 )continue;
            for(int k = dp[i-1].size() - 1; k >= 1; --k){
                if( k % 2 or j + k/2 >= dp[i].size())continue;
                if(dp[i-1][k] == 0)continue;
                dp[i][k/2 + j] += dp[i][j] * dp[i-1][k];
                dp[i][k/2 + j] %= mod;
            }
        }
    }
    int ans = 0;
    for(int i = 0;  i < dp.size(); ++i){
        ans += dp[i][1];
        ans %= mod;
    }
    cout << ans << endl;
}