Submission

PPPPPPPPPP-P-PP-

Score: 130

User: lufychop

Problemset: Chocolate

Language: cpp

Time: 0.177 second

Submitted On: 2025-03-17 12:29:06

#include <bits/stdc++.h>

using namespace std;

long long n,k,c,l,h,sum=0,mod=1e9+7;
vector<long long> a(5001);
vector<long long> p(5001,-1);
vector<long long> ml(5001,6000);
vector<long long> mr(5001,-1);
vector<long long> qs(5001,0);
vector<long long> dp(5001,0);

int main(void)
{
	cin>>n>>k>>c;
	p[0]=(c==0);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		p[i]=1;
	}
	cin>>l>>h;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<c;j++)
		{
			if(p[i]*i>2e9)
			{
				break;
			}
			p[i]=p[i]*i;
		}
	}
	for(int i=1;i<=n;i++)
	{
		sum=0;
		for(int j=i;j<=n;j++)
		{
			if(p[j-i]==-1)
			{
				break;
			}
			if(sum+p[j-i]*a[j]>2e9)
			{
				break;
			}
			sum=sum+p[j-i]*a[j];
			if(l<=sum && sum<=h)
			{
				ml[j]=min(ml[j],(long long)i);
				mr[j]=max(mr[j],(long long)i);
				if(i==1)
				{
					dp[j]=1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		qs[i]=qs[i-1]+dp[i];
		//cout<<ml[i]<<" "<<mr[i]<<"\n";
	}
//	for(int j=1;j<=n;j++)
//	{
//		cout<<dp[j]<<" ";
//	}
//	cout<<"\n";
	for(int i=2;i<=k;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(ml[j]>mr[j])
			{
				dp[j]=0;
				continue;
			}
			else
			{
				dp[j]=qs[mr[j]-1]%mod-qs[max((long long)0,ml[j]-2)]%mod;
				dp[j]=dp[j]%mod;
			}
		}
		for(int j=1;j<=n;j++)
		{
			//cout<<dp[j]<<" ";
			qs[j]=qs[j-1]+dp[j]%mod;
			qs[j]=qs[j]%mod;
		}
		//cout<<"\n";
	}
	cout<<dp[n]%mod;
	return 0;
}
/*
8 3 2
7 9 1 3 3 6 2 9
4 64

0 1 4 9 16 25 36 49 64

  0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 1 1 1 0 0 0 0
2 0 0 0 0 0 1 2 1 0
3 0 0 0 0 0 0 1 1 3
*/