Cerinta completa

One day, Wet Shark was given an array . As always, he started playing with its subsequences.

When you came to know about this habit, you presented him a task of finding all pairs of subsequences, , which satisfies all of the following constraints. We will represent a pair of subsequence as and

  • and must be of same length, i.e., .

Please help Wet Shark determine how many possible subsequences and can exist. Because the number of choices may be big, output your answer modulo .

Note:

  • Two segments are different if there’s exists at least one index such that element is present in exactly one of them.
  • Both subsequences can overlap each other.
  • Subsequences do not necessarily have to be distinct

Input Format

The first line consists of 3 space-separated integers , , , where denotes the length of the original array, , and and are as defined above.
The next line contains space-separated integers, , representing the elements of .

Constraints

Output Format

Output total number of pairs of subsequences, , satisfying the above conditions. As the number can be large, output it’s modulo

Sample Input 0

4 5 3
1 1 1 4

Sample Output 0

3

Explanation 0

For array there are three pairs of subsequences:

Limbajul de programare folosit: cpp14

Cod:

#include <cstdio>
#include <cstring>

int dp[4010][102];
int a[102];
const int MOD = (1e9) + 7;

int main() {
	int m, r, s;
	while (scanf("%d%d%d",&m,&r,&s) != EOF) {
		for (int i = 0 ; i < m ; ++i)
			scanf("%d", &a[i]);
		if (r == 0 && s == 0) {
			printf("0\n");
			continue;
		}
		if ((r + s) % 2 == 1 || r < s) {
			printf("0\n");
			continue;
		}

		int maxS = (r + s + 1) / 2;
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for (int i = 0 ; i < m ; ++i) {
			for (int sum = maxS ; sum >= 0 ; --sum) {
				if (sum + a[i] > maxS) continue;
				for (int cnt = 0 ; cnt <= i ; ++cnt) {
					dp[sum+a[i]][cnt+1] += dp[sum][cnt];
					dp[sum+a[i]][cnt+1] %= MOD;
				}
			}
		}
		int total = 0;
		for (int cnt = 0 ; cnt <= m ; ++cnt) {
			total += (int)((long long)dp[(r+s)/2][cnt] * dp[(r-s)/2][cnt] % MOD);
			total %= MOD;
		}
		printf("%d\n", total);
	}
	return 0;
}

Scor obtinut: 1.0

Submission ID: 464650244

Link challenge: https://www.hackerrank.com/challenges/wet-shark-and-two-subsequences/problem

Wet Shark and Two Subsequences