Submission

xPPPPxPPPPPPPPPP

Score: 140

User: lufychop

Problemset: Chocolate

Language: cpp

Time: 0.118 second

Submitted On: 2025-03-14 13:14:46

#include <bits/stdc++.h>

using namespace std;

int n,k,c,l,h,mod=1e9+7;
vector<int> p(2500);
vector<int> a(2500);
vector<vector<int>> dp(2500,vector<int>(2500,-1));

int test(int cnt,int t)
{
	if(t==n)
	{
		return cnt==k;
	}
	if(cnt==k)
	{
		return 0;
	}
	if(dp[cnt][t]!=-1)
	{
		return dp[cnt][t]%mod;
	}
	long long ans=0;
	long long sum=0;
	for(int i=t;i<n;i++)
	{
		sum=sum+p[i-t]*a[i];
		if(sum>h)
		{
			break;
		}
		else if(sum>=l)
		{
			ans=ans+test(cnt+1,i+1)%mod;
			ans=ans%mod;
		}
	}
	dp[cnt][t]=ans;
	return ans;
}

int main(void)
{
	cin>>n>>k>>c;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		p[i]=1;
		for(int j=0;j<c;j++)
		{
			p[i]=p[i]*i;
		}
	}
	cin>>l>>h;
	cout<<test(0,0);
	return 0;
}
/*
8 3 2
7 9 1 3 3 6 2 9
4 64
*/
/*
1
1

1 2
4 3
  7
  
1 2 3 2
6 5 4
7 8 9
 15 9

1 2 3 4 4 4
8 7 6 5
9 2 3 4
0 1 6 5
  1  11

1 2 3 4 5 6 6 2
0 9 8 7 6
1 6 7 8 9
2 5 2 1 0
3 4 3 4 5
  7   7 5

1 2 3 4 5 6 8 8 4 4
2 1 0 9 8 7
3 0 1 2 3 4
4 9 8 7 6 5
5 8 9 2 3 4
6 7 0 1 6 5
 13   1  11

1 2 3 4 5 6 7 10 10 6 6 2
4 3 2 1 0 9 8
5 4 5 6 7 8 9
6 3 4 3 2 1 0
7 2 5 0 1 2 3
8 1 6 9 6 5 4
9 0 7 8 7 8 9
  9  15  15 9

1 2 3 4 5 6 7 8 12 12 8 8 4 4
6 5 4 3 2 1 0 9
7 8 9 0 1 2 3 4
8 7 0 9 8 7 6 5
9 6 1 8 9 0 1 2
0 5 2 7 6 5 4 3
1 4 3 6 7 0 1 2
2 3 4 5 8 9 4 3
  5   9  17   7

1 2 3 4 5 6 7 8 9
8 7 6 5 4 3 2 1 0 
9 2 3 4 5 6 7 8 9
0 1 6 5 4 3 2 1 0
1 0 7 6 7 8 9 0 1
2 9 8 5 6 5 4 3 2
3 8 9 4 7 2 3 4 5
4 7 0 3 8 1 8 7 6
5 6 1 2 9 0 9 0 1
 11   3   9   9 1


 1  1
 2  7
 3 24
 4 12
 5 19
 6 25
 7 48
 8 38
 9 33
10 53

















2 3
-3 -6 -3
2 2 -3

    0  1  2  3  4
 0  0  0  0  0  0
 1  0 -3 -9-12
 2  0 -1  1 -2
 3  0  
 4  0
 
 4 3
-3 -6 -3
2 2 -3
-8 -8 -8
1 1 1
 
    0  1  2  3  4
 0  0  0  0  0  0
 1  0 -3 -9-12
 2  0 -1  1 -2
 3  0 -9 -7-10
 4  0 -8 -6 -9











*/