CODE THANKS FESTIVAL 2018(Parallel)

E - Union (400)

E - Union

概要

数列が与えられる。からまでの整数について、下記操作を考える。

• 整数を個以下の個数書き出す。
• 書き出した整数について、整数が2つあれば、その2つを消し、かわりにを1つ書き出す。

この操作を繰り返し、最終的に書き出された整数が1つになる場合の最初の整数の書き出し方は何通りか。(modで解答)

制約

方針

下記のDP配列を考える。
：数のみが個書き出されている場合の数
このDP配列は下記のように遷移させることができる。

のループは、以下の数値により作られたの場合の数を足してゆく。
のループは、を個まで書くことができるため、その場合の数を反映している。

最終的には数が1個書き出されていればよいため、解答はである。
また、以上の数については、までのDP配列の更新とし、このとき2のべき乗個書き出されていればよいため、
を追加で加える。

感想

下記ブログを参考にしました。
tutuz.hateblo.jp

解答

Submission #3928701 - CODE THANKS FESTIVAL 2018(Parallel)

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
ll MOD = 1e9+7;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int t;
	cin >> t;
 
	vector<ll> a(t);
	rep(i, t) cin >> a[i];
 
	int dp[500][1000];
	dp[0][0] = 1;
	for(int i = 0; i < t; i++){
		for(int j = 0; j <= 300; j++){
			for(int k = 0; k <= a[i]; k++){
				dp[i+1][j+k] += dp[i][2*j];
				dp[i+1][j+k] %= MOD;
			}
		}
	}
 
	ll ans = 0;
	for(int i = 0; i <= t; i++){
		ans += dp[i][1];
		ans %= MOD;
	}
 
	for(int i = 2; i < 1000; i *= 2){
		ans += dp[t][i];
		ans %= MOD;
	}
 
	cout << ans << endl;
}