Как понять условие задачи?

wataru, Спасибо большое за предложенное решение и развернутые комментарии! Недавно столкнулся с этой же задачей. Ограничения были следующие:
Память - 512Мб
Время выполнения - 1 сек. (Intel(R) Xeon(R) CPU E5-2660 @ 2.20GHz, 20480KB cache, виртуализация на 1 ядре, 4GB RAM).
На моей машине (i9-9900k @ 4.90GHz) на решение с наибольшей колодой (50 типов карт по 10 каждого типа) уходит чуть более 1,8 сек. Возможно ли как-то еще оптимизировать решение?

#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <chrono> // for std::chrono functions

class Timer
{
private:
	// Type aliases to make accessing nested type easier
	using clock_t = std::chrono::high_resolution_clock;
	using second_t = std::chrono::duration<double, std::ratio<1> >;

	std::chrono::time_point<clock_t> m_beg;

public:
	Timer() : m_beg(clock_t::now())
	{
	}

	void reset()
	{
		m_beg = clock_t::now();
	}

	double elapsed() const
	{
		return std::chrono::duration_cast<second_t>(clock_t::now() - m_beg).count();
	}
};

long long modExp(long long x, long long y, long long N)
{
	if (y == 0) return 1;
	long long z = modExp(x, y / 2, N);
	if (y % 2 == 0)
		return (z * z) % N;
	else
	{
		long long zz{ (z * z) % N };
 		return (x * zz) % N;
	}
}

long long modFactorial(int n, long long N)
{
	static std::vector<long long> memory(251, -1);
	if (n < 251)
	{
		if (memory[n] == -1)
		{
			memory[n] = (n == 1 || n == 0) ? 1 : (modFactorial(n - 1, N) * n) % N;
		}
		return memory[n];
	}
	else 
		return (modFactorial(n - 1, N) * n) % N;
}

long long revModFactorial(int n, long long N)
{
	static std::vector<long long> revMemory(251, -1);
	if (n < 251)
	{
		if (revMemory[n] == -1)
		{
			revMemory[n] = (revModFactorial(n + 1, N) * (n + 1)) % N;
		}
		return revMemory[n];
	}
	else
		return modExp(modFactorial(n, N), N - 2, N);
}


long long modC(int n, int k, long long N) {
	static	std::vector< std::vector<long long>> modCmemory (251,
			std::vector<long long>(251, -1));
	if (n < k)
		return 0;
	else if (n == k)
		return 1;
	else if (modCmemory[n][k] == -1)
	{
		long long denum{ (revModFactorial(k, N) * revModFactorial(n - k, N)) % N };
		modCmemory[n][k]= (modFactorial(n, N) * denum) % N;
	}
	return modCmemory[n][k];
}

int sumUpTo(int k, std::vector<int>& a)
{
	static std::vector<int> sumUpToMemory(k + 1, -1);
	
	if (sumUpToMemory[k] == -1)
	{
		if (k == 0) 
			sumUpToMemory[k] = 0;
		else
		{
			int sum{};
			sum = a[k] + sumUpTo(k - 1, a);
			sumUpToMemory[k] = sum;
		}
	}
	return sumUpToMemory[k];
}

long long DP(int k, int t, int i, int j, std::vector<int>& a, long long N)
{
	static	std::vector< std::vector< std::vector< std::vector<long long>>>> DPmemory(51,
			std::vector< std::vector< std::vector<long long>>>(251,
			std::vector< std::vector<long long>>(51,
			std::vector<long long>(51, -1))));

	if ((k < 0) || (t < 0) || (i < 0) || (j < 0)) return 0;

	if (DPmemory[k][t][i][j] == -1)
	{
		if (k == 0)
		{
			if ((t == 0) && (i == 0) && (j == 0)) DPmemory[k][t][i][j] = 1;
			else DPmemory[k][t][i][j] = 0;
		}
		else
		{
			long long sum{};
			int min{ std::min(a[k], t) };
			for (int v{ 0 }; v <= min; ++v)
			{
				long long tempC{ (modC(t, v, N) * modC(sumUpTo(k, a) - t, a[k] - v, N)) % N };
				if (tempC > 0)
					sum = (sum + DP(k - 1, t - v, i - (v > 0), j - (v < a[k]), a, N)* tempC) % N;

			}
			DPmemory[k][t][i][j] = sum;
		}
	}
	return DPmemory[k][t][i][j];
}



int main()
{
	//Performance timers
	Timer t;
	Timer total;

	//Input optimization
	std::ios_base::sync_with_stdio(false);

	//Reading from file
	std::ifstream input("input.txt");
	std::stringstream strStream;
	strStream << input.rdbuf();

	int n;										//n - number of cardTypes
	strStream >> n;
	std::vector<int> deck(n+1);
	int deckSize{};
	for (int cardType{ 1 }; cardType <= n; ++cardType)
	{
		strStream >> deck[cardType];
		deckSize += deck[cardType];
	}

	std::cout << "Time elapsed (read): " << t.elapsed() << " seconds\n";
	t.reset();

	long long N{ 1000000007 };
	long long p{}; 
	long long rq{ revModFactorial(deckSize, N) };
	for (int cardType{ 1 }; cardType <= n; ++cardType)
	{
		rq = (rq * modFactorial(deck[cardType], N)) % N;
	}



	for (int i{ 1 }; i <= n; ++i)
	{
		p = (p + DP(n, deckSize / 2, i, i, deck, N)) % N;
	}

	std::cout << "Time elapsed (count): " << t.elapsed() << " seconds\n";
	t.reset();

	std::cout << (p * rq) % N << "\n";

	std::cout << "Time elapsed (answer): " << t.elapsed() << " seconds\n";
	std::cout << "Time elapsed (total): " << total.elapsed() << " seconds\n";


	return 0;
 }