Submission #3671081

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#include <bitset>
#include <iterator>	
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#define INF 2000000000
#define MOD 1000000007
#define sym cout<<"---------"<<endl;
#define ll long long
#define mk make_pair
#define en endl
#define RE return 0
#define int ll
#define P pair<int,int>
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int gcd(int a,int b){if(a%b==0){return b;}else return gcd(b,a%b);}
int lcm(int a,int b){if(a==0){return b;} return a/gcd(a,b)*b;}

#define MAX 100005
int n;
int a[305];
int dp[305][MAX];

int saiki(int now, int number){
	if(dp[now][number]!=-1){
		return dp[now][number];
	}else if(number==1){
		return dp[now][number]=1;
	}else if(now==n){
		return dp[now][number]=__builtin_popcount(number)==1;
	}else if(number%2==1){
		return dp[now][number]=0;
	}
	
	int nxt=number/2;
	int ans=0;
	for(int i=0; i<=a[now+1]; i++){
		ans+=saiki(now+1, nxt+i)%MOD;
	}
	return dp[now][number]=ans%MOD;
}

signed main(){
	cin>>n;
	for(int i=0; i<n; i++) cin>>a[i+1];
	memset(dp, -1, sizeof(dp));
	int ans=0;
	for(int i=0; i<=a[1]; i++){
		ans+=saiki(1, i)%MOD;
	}
	cout<<ans%MOD<<en;
}

Submission Info

Judge Result