Cerinta completa

Tim is visiting his grandma for two days and is bored due to the lack of the electricity over there. That’s why he starts to play with grandma’s colorful candle collection.

He aligned the candles from left to right. The th candle from the left has the height and the color , an integer ranged from 1 to a given , the number of colors.

Now he stares at the sequence of candles and wonders, how many strictly increasing ( in height ) colorful subsequences are there? A subsequence is considered as colorful if every of the colors appears at least one times in the subsequence.

As the number of subsequences fulfilling the requirement can be large, print the result modulo .

Input Format

On the first line you will be given and , then lines will follow. On the th line you will be given two integers and .

Constraints

Output Format

Print the number of strictly increasing colorful subsequences modulo .

Sample Input

4 3
1 1
3 2
2 2
4 3

Sample Output

2

Explanation

In the first sample the only two valid subsequences are (1, 2, 4) and (1, 3, 4).

Limbajul de programare folosit: cpp14

Cod:

#include<iostream>
#include<cstring>
using namespace std;

int h[50000], c[50000];

const int MAXN = 50010;
const int MOD = 1000000007;

class FenwickTree
{
private:
	long long tree[MAXN];

public:
	FenwickTree()
	{
		memset(tree, 0, sizeof(tree));
	}

	long long get(int idx)
	{
		return query(idx) - query(idx - 1);
	}

	void set(int idx, long long val)
	{
		long long curr = get(idx);
		update(idx, val - curr);
	}

	void update(int idx, long long val)
	{
		while (idx <= MAXN)
		{
			tree[idx] = (tree[idx] + val) % MOD;
			idx += (idx & -idx);
		}
	}

	long long query(int idx)
	{
		long long sum = 0;
		while (idx > 0)
		{
			sum = (sum + tree[idx]) % MOD;
			idx -= (idx & -idx);
		}
		return sum;
	}
};

FenwickTree s[128];

int main()
{
	int n, k;
	cin >> n >> k;
	s[0].update(1, 1);
	for (int i = 0; i < n; i++)
	{
		cin >> h[i] >> c[i];
		h[i]++;  c[i]--;
		for (int j = 0; j < (1 << k); j++)
		{
			long long val = s[j].query(h[i] - 1);
			s[j | (1 << c[i])].update(h[i], val);
		}
	}
	cout << s[(1 << k) - 1].query(50001) << endl;
	return 0;
}

Scor obtinut: 1.0

Submission ID: 464604968

Link challenge: https://www.hackerrank.com/challenges/candles-2/problem

Candles Counting