#24488 Drought

문제를 요약하면, 수열에서 인접한 두 수를 골라 1빼는 연산을 원하는 만큼 시행하여 수열의 모든 원소를 동일하게 만들 수 있도록 하는 수열의 개수 단 hi는 0이상 Hi이하 정수라는 제한 조건이 달려있다. 

 

저 연산을 뚫어지게 살펴보면 다음과 같은 관찰을 할 수가 있다.

h를 결정했다고 치고, 최종적으로 같아지게 되는 수열의 원소 값을 x라고 두면, 이 연산을 시행해서 모든 원소를 x로 만들 수 있는지를 판단하기는 쉽다.

a(i)=h(i)와 h(i+1)을 골라 연산을 시행하는 경우의 수. 라고 정의하자

x=h(1)-a(1)가 되어서, a(1)가 고정된다. 그런데,

x=h(2)-(a(1)+a(2))이므로, a(1)이 결정되면 a(2)도 결정된다. (지금 상태에서 h와 x는 상수이므로)

마찬가지로 모든 a값들이 결정되는데, 마지막 원소인 x=h(n)-a(n-1)로 a(n-1)도 결정된 상태이다.

따라서 앞에서부터 쭉 구해온 값과 뒤에 값이 같게 되는지를 판정하면 된다.

 

이렇게 h가 고정되어 있고, x가 고정되어 있다면, 이게 가능한지를 판정하는 것은 쉽다.

그런데 문제는 h도 변하고 x도 변한다.

문제 제한 자체가 h의 크기와 x가 작다. (n<=100, Hi<=1000)
따라서 x를 고정하고 dp를 돌린다는 첫번째 아이디어 까지는 쉽게 도달할 수 있다.

그런데 문제가 있다.

 

x가 고정되었는데, h는 동일한 경우는 중복해서 세어진다는 점이다.

이를 어떻게 타파할지는 다음과 같다.

 

 

우선 n이 짝수일때

x는 가변이 아니라 0으로 고정해도 동치이다.

즉 수열의 모든 원소를 x로 만들 수 있다는 것은, i와 i+1을 섞어서 연산을 시행해주면 모든 원소를 다시 0으로 만들 수 있으므로 n이 짝수 일때는 손쉽게 x를 0으로 고정해서 세어주면 된다.

 

n이 홀수일때

이때가 중요한데, 여기서 중요한 점은 짝수 경우와 다르게 x가 다른데 h가 동일한 경우는 없다.

그 직관은 다음과 같이 파악할 수 있는데, 어떤 x가 존재해서, 수열의 모든 원소가 x x x x x x x가 된다면,

이 수열에 연산을 어떻게 적용하던 y y y y y y y (y<x)인 꼴로 만들 수 없다.

증명은 생략...

따라서 n이 홀수 일때는, x와 h를 고정하고 dp를 돌려주면 된다.

 

#include<bits/stdc++.h>
//#define double long double
//T.erase(unique(T.begin(),T.end()),T.end());
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 2e5 + 100, inf = (ll)1e9 * (ll)1e9 + 7, mod = 1e9 + 7, sqrtN = 320;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, base, ans, q;
ll gcd(ll x, ll y) {
	if (!y)return x;
	return gcd(y, x % y);
}
ll pre[102][1005];
void solve() {
	cin >> n;
	vector<ll>v(n + 1);;
	base = inf;
	for (int i = 1; i <= n; i++)cin >> v[i], base = min(base, v[i]);
	if (n % 2) {
		for (int x = 0; x <= base; x++) {
			memset(pre, 0, sizeof(pre));
			for (int i = 0; i <= v[1]-x; i++)pre[1][i] = 1;
			
			for (int i = 1; i + 1 < n; i++) {
				for (int j = 0; j <= 1000; j++) {
					ll now = pre[i][j], l, r;
					if (j+x > v[i + 1])continue;
					pre[i + 1][0] = (pre[i + 1][0] + now) % mod;
					r = v[i + 1] - j - x;
					pre[i + 1][r + 1] = (pre[i + 1][r + 1] - now + mod) % mod;
				}
				for (int j = 1; j <= 1000; j++)pre[i + 1][j] = (pre[i + 1][j] + pre[i + 1][j - 1]) % mod;
			}
			
			for (int j = 0; j <= v[n]-x; j++)ans = (ans + pre[n - 1][j]) % mod;
		}
		if (n == 1)ans = v[1] + 1;
	}
	else {
		for (int i = 0; i <= v[1]; i++)pre[1][i] = 1;
		for (int i = 1; i+1 < n; i++) {
			for (int j = 0; j <= 1000; j++) {
				ll now = pre[i][j], l, r;
				if (j > v[i + 1])continue;
				pre[i + 1][0] = (pre[i + 1][0] + now) % mod;
				r = v[i + 1] - j;
				pre[i + 1][r + 1] = (pre[i + 1][r + 1] - now + mod) % mod;
			}
			for (int j = 1; j <= 1000; j++)pre[i + 1][j] = (pre[i + 1][j] + pre[i + 1][j - 1]) % mod;
		}
		for (int j = 0; j <= v[n]; j++)ans = (ans + pre[n-1][j]) % mod;
	}

	cout << ans;
	cout << '\n';
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//cin >> tc;
	while (tc--)solve();
}