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

Question

Proshka17 @Proshka17

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

Добрый день!
Есть задача:

Я написал код для подсчета вероятности ничьи, но не понимаю что именно нужно вывести:

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <string>
#include <fstream>
#include <sstream>

using namespace std;


class Sol {
public:

  int num = 0;

  vector<int> starter;
  int otv = 0;
  int border = 0;
  int summer = 0;

  void rec(vector<int> vec, string posl, int counter, int mn) {

    if (counter == border) {
      int uniqleft = 0;
      int uniqright = 0;
      for (int i = 0; i < starter.size(); ++i) {
        if (starter[i] != vec[i]) uniqleft++;
        if (vec[i] > 0) uniqright++;
      }
      if (uniqleft == uniqright) otv += mn;
      summer += mn;
      cout << num << ": " << posl << " - " << mn << "| " << uniqleft << "-" << uniqright << "\n";
      num += mn;
      return;
    }



    for (int i = 0; i < vec.size(); ++i) {
      if (vec[i] > 0) {
        vec[i]--;
        rec(vec, posl + to_string(i + 1), counter + 1, mn * (vec[i] + 1));
        vec[i]++;
      }
    }

  }

};


int main() {

  ifstream f("input.txt");
  Sol s;

  int count;
  f >> count;
  vector<int> vec;
  int sch = 0;
  for (int i = 0; i < count; ++i) {
    int tmp;
    f >> tmp;
    s.starter.push_back(tmp);
    vec.push_back(tmp);
    sch += tmp;
  }

  s.border = sch / 2;
  s.rec(vec, "", 0, 1);
  cout << (double)s.otv / s.summer;


  //cout << s.bad;



  return 0;
}

Подскажите пожалуйста, как из полученной мной вероятности ничьи получить требуемый ответ?

Вопрос задан более трёх лет назад
898 просмотров

3 комментария

Подписаться 2 Простой 3 комментария

Решения вопроса 1

21 комментарий

Proshka17 @Proshka17 Автор вопроса

Спасибо за ответ!
Буду разбираться

Написано более трёх лет назад
Proshka17 @Proshka17 Автор вопроса

Добрый день!
Подскажите пожалуйста по поводу уменьшения уникальных карт для первого и второго игрока, а то я не совсем понял.
DP(k-1, t-v, i - {v>0}, j-{v < a[k]}) * C(t, v) * C(a[1]+a[2]+...+a[k]-t, a[k]-v)
Почему мы вычитаем 1 из количества уникальных для первого игрока, если v>0?
Например, если v=0, то это значит, что все карты этого типа достанутся второму игроку и у первого игрока не будет карт этого типа, а значит, что надо вычесть 1. При этом получается, что у второго игрока мы уменьшим количество уникальных карт, хотя все карты этого типа попадут к нему. Или я не правильно понял?

Написано более трёх лет назад
Wataru @wataru Куратор тега C++

Proshka17 Надо бы уточнить, что я понимаю трактую "сколько уникальных карт" в условии задачи как "сколько различных типов карт игрок получил". {1,1,2,2,3} - это 3 уникальные карты. Если понимать условие по-другому (сколько типов карт у игрока ровно в одном экземпляре), то надо чуть-чуть подправить вычисления. Вместо условия v>0 будет v==1. Вместо v
Такая трактовка следует из вашего кода, вы там счетчик уникальных увеличиваете, если игроку хоть одна карта досталась.

Теперь ответ на ваш вопрос.
Если v>0, то первый игрок получил хоть одну карту последнего типа (k). Мы же эти карты выбрасываем из рассмотрения. Что остается у первого игрока? Сколько у него будет уникальных? Именно i - {v>0}, ведь с этими последними картами у него i уникальных. Значит если ему досталась хоть одна карта последнего типа, то карты этого типа прибавили 1 к i. Значит, после выкидывания остается i-1. Аналогично у второго игрока. В j последние карты подсчитаны как +1, если хоть одна карта ему досталась. Это в случае, если v

Написано более трёх лет назад
Proshka17 @Proshka17 Автор вопроса

Понял, спасибо.
А условие выхода из рекурсии такое?
if (k==-1 || t==0) return 1;

Написано более трёх лет назад

Proshka17 @Proshka17 Автор вопроса

Посмотрите пожалуйста на код, правильно ли я понял про суммирование все вариантов? Ответ пока не правильный выдает.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <string>
#include <fstream>
#include <sstream>
#include <iomanip>

using namespace std;


class Sol {
public:

  vector<int> vec;
  int sum = 0;
  vector<long long> facts;
  vector<long long> re_facts;
  long long Z = 1000000007;
  long long N = 0;
  long long product_of_facts = 1;
  long long inv_N = 1;

  long long Factorial(int n)
  {
    long long f = 1;
    if ((n == 0) || (n == 1))
      f = 1;
    else
      for (int i = 1; i <= n; i++) {
        f *= i;
        f = f % Z;
      }
        
    return f;
  }

  long long C(long long n, long long k) {
    return facts[n] * re_facts[k] * re_facts[n - k];
  }

  int DP(int k,int t,int i,int j){
    if (k==-1 || t==0) return 1;

    for (int v = 0; v < min(vec[k], t); ++v) {
      int del1 = 0;
      int del2 = 0; 
      if (v > 0) del1 = 1;
      if (v<vec[k]) del2 = 1;
      sum += DP(k-1,t-v,i-del1,j-del2)*C(t,v)*C(N-t,vec[k]-v);
    }

    return 1;
  }




  long long gcd(long long a, long long b, long long& x, long long& y) {
    if (a == 0) {
      x = 0; y = 1;
      return b;
    }
    long long x1, y1;
    long long d = gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
  }


};


int main() {

  ifstream f("input.txt");
  Sol s;
  long long count;
  f >> count;

  for (int i = 0; i <= 500; ++i) {
    s.facts.push_back(s.Factorial(i));
    long long x;
    long long y;
    s.gcd(s.facts[s.facts.size() - 1] % s.Z, s.Z, x, y);
    if (x < 0) x += s.Z;
    s.re_facts.push_back(x);
  }


  for (long long i = 0; i < count; ++i) {
    long long tmp;
    f >> tmp;
    s.vec.push_back(tmp);
    s.product_of_facts *= s.facts[tmp];
    s.product_of_facts = s.product_of_facts % s.Z;
    s.N += tmp;
  }

  long long x;
  long long y;
  s.gcd(s.N % s.Z, s.Z, x, y);
  if (x < 0) x += s.Z;
  s.inv_N = x;

  long long n = s.vec.size();

  

  for (int i = 1; i < s.vec.size();++i) s.DP(s.vec.size()-1, s.N / 2, i, i);

  cout << s.sum;
  return 0;
}

Написано более трёх лет назад

Wataru @wataru Куратор тега C++
Proshka17,
Нет, условие выхода я написал в секции "база:"

DP(0,0,0,0) = 1, DP(0,*,*,*) = 0

Т.е. должно быть что-то вроде:

if (k == -1) { // у вас индексация с 0, у меня в формулах с 1. return (t==0 && j==0 && i == 0) ? 1 : 0; }

Далее по коду, Тут много нареканий:

Вы где C() считаете, надо после КАЖДОЙ арифметической операции брать по модулю а то будет переполнение. Т.е. надо писать что-то вроде (a*b %z ) * c % z.

Факториалы не надо так считать, выглядит ужасно. делайте лучше push_back((facts.back() * i)%z). И гоните цикл от 1, предварительно сделав facts,push_back(1) и re_facts.push_back(1);

Теперь про динамику. Почитайте что-нибудь про динамическое программирование. Самое важное в рекурсии сделать мемоизацию. Без этого у вас не динамика а почти полный перебор. Вам нужен четырехмерный массив размерностью под максимальные значения четырех параметров функции, который изначально заполнен -1 (это число вы никак в своих вычислениях не получите, они же по модулю). В начале рекурсивной функции вы смотрите на значение массива [k,t,i,j]. Если там не -1, то сразу возвращаете его. Иначе считаете функцию как у вас и в конце, перед return sum (кстати, почему у вас 1 возвращается всегда?) запишите sum в массив. Таким образом для каждого набора параметров ("состояния") вы подсчитаете функцию максимум один раз.

У вас путаница - похоже, вы в каждом вызове DP() суммируете в ответ к задаче, но это же не работает. Вам в ответ надо взять сумму лишь некоторых (Не всех!) Dp(*,*,*,*). Поэтому каждая DP должна считать сумму в локальной переменной и вернуть ее. DP - функция, которая возвращает количество чего-то там, что я в первом ответе написал. В main() вы должны в цикле значения возвращенные DP() просуммировать.

Далее, вы где C() перемножаете и сумму считаете надо, опять же, после каждой операции брать по модулю Z.

Далее вы во втором С() вызываете от N, что неправильно. Посмотрите на мою формулу, там сумма a[1]..a[k], не до n, а до k! Нужно вычитать t из суммы пока что рассмотренных карт. Т.е. vec[0]...vec[k-1]. Можете эти кумулятивные суммы тоже предподсчитать.

Еще, глаза режет - min() в условии цикла вынесите за цикл в локальную переменную.
И цикл надо гнать до этого min() включительно. Т.е должно быть v<=... в условии. Вы можете все карты k-ого типа отдать первому игроку (но не более t).

И еще, вы забыли в конце "поделить" сумму на общее количество вариантов.

НО! Рекурсивная реализация у вас может не зайдет по memory limit exceeded. Потому что вам надо завести массив 51x251x51x51 long (можно хранить и возвращать 4-х байтное, ведь модуль влезает). Это 135mb, может не влезть. Я не знаю ограничения. Если влезет - хорошо. Если нет, попробуйте переписать это как динамику снизу-вверх. Я привел рекурсивное определение, потому что его проще понять, как мне кажется.
Написано более трёх лет назад

alexbirdie @alexbirdie

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;
 }

Написано более трёх лет назад

Wataru @wataru Куратор тега C++
Во первых, глаза режет реализация revModFactorial. Просто, если не подсчитано значение, берите ModFactorial и возводите в степень N-2. И сделайте массивы для факториалов до 500, все-таки такие числа попадаются в формулах. Но это придирки.

Попробуйте вместо статических векторов завести глобальные массивы фиксированного размера. Где-то в main() перед всеми вычислениями сделайте memset(array, -1, sizeof(array)).

Попробуйте вместо sumupto() один раз подсчитать глобальный массив частичных сумм b[] и просто обращаться к нему напрямую:

int b [51]; ... b[0] = a[0]; for (i = 1; i < n; i++) b[i] = b[i-1] + a[i];

Так же, предподсчитайте факториалы, обратные к ним и сочетания в глобальных массивах циклами до основного DP. Таким образом вы выкинете вызовы функций и проверки на подсчитанность, которые совсем лишние.

Надо по максимуму соптимизировать основной цикл (он у вас по v). Никаких функций кроме DP() внутри быть не должно.

Так-то по сложности должно с лихвой помещаться.

UPD: и уменьшите количество параметров у DP. Входные данные a и N - можно сделать глобальными переменными.
Написано более трёх лет назад
Proshka17 @Proshka17 Автор вопроса

alexbirdie, Добрый день!
Мне опять понадобилось решить данную задачу, но ваше решение не проходит по скорости.
Получилось ли у вас ускорить решение?

Написано более трёх лет назад
Wataru @wataru Куратор тега C++

Proshka17, Возможно вы что-то не так реализовали. Предложенное решение через динамическое программирование для упомянутых ограничений должно укладываться в любые разумные ограничения по времени.

Можно соптимизировать, если вместо двух последних параметров (сколько уникальных карт у одного и у второго) считать один параметр от -50..+50 - на сколько уникальных карт у первого больше чем у второго. Пересчет чуть чуть меняется, и это будет ускорение в 25 где-то раз.

Еще можно ускорить если пустить динамику снизу вверх циклами и хранить только 2 последние строки. Так памяти будет потреблятся в 25 раз меньше и вычисление будет более дружественно кэшу.

Написано более трёх лет назад
Proshka17 @Proshka17 Автор вопроса

wataru, Добрый день!
Я попробовал решение, которое предложил alexbirdie, но пока получил Time Limit на 13 тесте.

Написано более трёх лет назад
Wataru @wataru Куратор тега C++

Proshka17, Замените 2 последних параметра в ДП (50х50) на один -50..50. Вместо количества уникальных карт у каждого игрока считайте, на сколько у первого игрока уникальных больше.

Пересчет меняется просто. Если где-то вызывается от (..x,y), то надо вызываться от x-y. Для запоминания в массиве прибавляйте 50 к индексу.

Написано более трёх лет назад

Proshka17 @Proshka17 Автор вопроса

wataru, Вроде сделал, но не могу понять пару моментов:

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



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, std::vector<int>& a, long long N)
{
  static	std::vector<std::vector<std::vector<long long>>> DPmemory(51,
    std::vector<std::vector<long long>>(251,
      std::vector<long long>(101, -1)));

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

  if (DPmemory[k][t][i+50] == -1)
  {
    if (k == 0)
    {
      if ((t == 0) && (i == 0) && (j == 0)) DPmemory[k][t][i+50] = 1;
      else DPmemory[k][t][i+50] = 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) - (v < a[k]), a, N)* tempC) % N;

      }
      DPmemory[k][t][i+50] = sum;
    }
  }
  return DPmemory[k][t][i+50];
}



int main()
{


  //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];
  }


  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, 0, deck, N)) % N;
  }


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



  return 0;
}

На что заменить
if ((k < 0) || (t < 0) || (i < 0) || (j < 0)) return 0;
С учетом нового значения i?
И на что заменить if ((t == 0) && (i == 0) && (j == 0)) DPmemory[k][t][i+50] = 1;

Написано более трёх лет назад

Proshka17 @Proshka17 Автор вопроса

if ((k < 0) || (t < 0) || (i < 0) || (j < 0)) return 0;
Навероне можно заменить на
if ((k < 0) || (t < 0) || (i < -50) || (i > 50) ) return 0;

Написано более трёх лет назад
Wataru @wataru Куратор тега C++

условие на i<0, j<0 в первой проверке можно заменить на проверку, что разница по модулю не больше k. Ведь если у вас k типов карт роздано, то вы сможете получить от -k...k перевеса, отдав все или ни одной уникальнойкарты первому игроку

Второе условие - это база, когда роздано 0 типов карт. В этом случае перевеса нет и у первого игрока 0 карт. Т.е. условие t==0 && i==0. Тогда ответ 1. Иначе - 0.

Написано более трёх лет назад

Proshka17 @Proshka17 Автор вопроса

wataru, Сделал, но ответ не правильный, хотя до исправлений был верный:

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



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, std::vector<int>& a, long long N)
{
  static	std::vector<std::vector<std::vector<long long>>> DPmemory(51,
    std::vector<std::vector<long long>>(251,
      std::vector<long long>(101, -1)));

  if ((k < 0) || (t < 0) || (i < -50) || (i > 50)) return 0;

  if (DPmemory[k][t][i+50] == -1)
  {
    if (k == 0)
    {
      if ((t == 0) && (i == 0) ) DPmemory[k][t][i+50] = 1;
      else DPmemory[k][t][i+50] = 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) - (v < a[k]), a, N)* tempC) % N;

      }
      DPmemory[k][t][i+50] = sum;
    }
  }
  return DPmemory[k][t][i+50];
}



int main()
{


  //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];
  }


  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, 0, deck, N)) % N;
  }


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



  return 0;
}

Ошибка для колоды
1 2 3
Выводит 0 вместо 100000001

Написано более трёх лет назад

Wataru @wataru Куратор тега C++

Proshka17, Похоже фигня вот тут:
DP(k - 1, t - v, i - (v > 0) - (v < a[k]), a, N)

В пересчете i флаги должы идти с разными знаками. Если первому игроку досталась карта - то +1, если второму, то -1 (ну, или наоборот). У вас же оба флага вычитаются.

Написано более трёх лет назад
Proshka17 @Proshka17 Автор вопроса
wataru, переделал вот так:

sum = (sum + DP(k - 1, t - v, i - (v > 0) + (v < a[k]), a, N)* tempC) % N;

Но ответ, все равно не правильный: 300000003
Вызов же я вроде правильно переделал?

for (int i{ 1 }; i <= n; ++i) { p = (p + DP(n, deckSize / 2, 0, deck, N)) % N; }
Написано более трёх лет назад
Wataru @wataru Куратор тега C++

Proshka17, Да, вызов не правильный же. Надо только один раз вызвать. Это раньше надо было перебирать, сколько карт им досталось. Теперь же достаточно просто зафиксировать разницу в 0. Т.е ответ - это просто один вызов.

Написано более трёх лет назад
Proshka17 @Proshka17 Автор вопроса

wataru, Получилось, огромное спасибо!

Написано более трёх лет назад
Proshka17 @Proshka17 Автор вопроса

wataru, Мне нужно решить еще одну задачу. Я никак не могу придумать решение быстрее n^2. Если посмотрите, буду очень благодарен!
Как решить задачу на c++ быстрее чем за n^2?

Написано более трёх лет назад

Пригласить эксперта

Ответы на вопрос 1

3 комментария

Proshka17 @Proshka17 Автор вопроса

Добрый день!
Сделал все по вашему алгоритму, на первых 5 тестах работает, а дальше у меня пока Time Limit вываливается

Написано более трёх лет назад
Wataru @wataru Куратор тега C++

Proshka17, Вы делаете что-то вроде полного перебора, а тут нужно комбинаторную магию и динамическое программирование применить. Я попозже распишу подробнее. Пока, напишите ограничения в задаче. Сколько карт всего, сколько типом может быть.

Сначала напишите "в даблах", когда у вас все числа с плавающей точкой и вы можете их умножать и делить. Потом примените хитрость из условия, что считать надо по модулю. Все числа целые. Вместо деления - умножайте на обратное по модулю. Обратное, как вам уже сказал Mercury13 , ищите расширенным алгоритмом эвклида. Это стандартный прием на соревнованиях, чтобы не требовать писать длинную арифметику.

Написано более трёх лет назад

Proshka17 @Proshka17 Автор вопроса

Добрый день!
Добавил ограничения для входных данных в вопрос.
Пока сделал код чуть быстрее, но все равно Time Limit(

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <string>
#include <fstream>
#include <sstream>
#include <iomanip>

using namespace std;


class Sol {
public:

  long long num = 0;

  vector<long long> starter;
  long long otv = 0;
  long long border = 0;
  long long summer = 0;
  unordered_map<long long, long long> unsetleft;
  unordered_map<long long, long long> unsetright;

  void rec(vector<long long> vec, long long counter, long long mn) {

   
    if (counter == border) {
      if (unsetleft.size() == unsetright.size()) {
        otv += mn;
      }
      summer += mn;
      return;
    }


    for (long long i = 0; i < vec.size(); ++i) {
      if (vec[i] > 0) {
        vec[i]--;
        if (unsetleft.find(i) == unsetleft.end()) {
          unsetleft.emplace(i, 1);
        }
        else {
          unsetleft[i]++;
        }

        long long mem = unsetright[i];
        if (vec[i] == 0) unsetright.erase(i);
        rec(vec, counter + 1, mn * (vec[i] + 1));
        if (vec[i] == 0) unsetright.emplace(i,mem);
        if (unsetleft[i] == 1) {
          unsetleft.erase(i);
        }
        else {
          unsetleft[i]--;
        }
        vec[i]++;
      }
    }

  }




  long long gcd(long long a, long long b, long long& x, long long& y) {
    if (a == 0) {
      x = 0; y = 1;
      return b;
    }
    long long x1, y1;
    long long d = gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
  }


};


int main() {

  ifstream f("input.txt");
  Sol s;

  long long count;
  f >> count;
  vector<long long> vec;
  long long sch = 0;
  for (long long i = 0; i < count; ++i) {
    long long tmp;
    f >> tmp;
    s.unsetright.emplace(i,1);
    vec.push_back(tmp);
    sch += tmp;
  }

  s.border = sch / 2;
  s.rec(vec, 0, 1);
  long long P = s.otv;
  long long Q = s.summer;
  long long Z = 1000000007;
  long long x;
  long long y;
  s.gcd(Q % Z, Z, x, y);
  double res = ((P % Z) * x) % Z;
  if (res < 0) res += Z;
  cout << fixed << setprecision(0) << res;


  //cout << s.bad;



  return 0;
}

Написано более трёх лет назад

Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации

Похожие вопросы

C++

+1 ещё

Простой
Рекурсивный ввод-вывод последовательности без использования массивов и списоков?
- 2 подписчика
- 3 часа назад
- 173 просмотра
0

ответов
C++

+2 ещё

Средний
Как сделать маштабирование относительно центра екрана?
- 1 подписчик
- 9 часов назад
- 46 просмотров
0

ответов
C++

Простой
Как составить план по изучению языка C++?
- 1 подписчик
- 22 часа назад
- 105 просмотров
2

ответа
Алгоритмы

Средний
Справится ли алгоритм с задачей по поиск слов в словаре?
- 1 подписчик
- вчера
- 66 просмотров
1

ответ
C++

+2 ещё

Простой
Как подключить библиотеку TgBot к срр проекту?
- 1 подписчик
- вчера
- 62 просмотра
1

ответ
C++

+2 ещё

Простой
Как выровнять по центру текст подсказки и вводимый текст в QTextEdit?
- 1 подписчик
- вчера
- 33 просмотра
1

ответ
C++

Простой
Как можно разделить данный код (см. ниже) по header'ам и cpp'ам, учитывая зависимости в нём?
- 1 подписчик
- вчера
- 65 просмотров
2

ответа
Алгоритмы

Простой
Как определить сложность алгоритма?
- 1 подписчик
- 16 апр.
- 101 просмотр
3

ответа
Windows

+1 ещё

Простой
Как исправить ошибку буфера с UART?
- 1 подписчик
- 15 апр.
- 145 просмотров
2

ответа
C++

Простой
Как вернуть двумерный массив?
- 1 подписчик
- 15 апр.
- 79 просмотров
3

ответа
Показать ещё Загружается…

Kotlin Backend-разработчик

vivaCRM • Москва

от 200 000 до 250 000 ₽

Backend разработчик

Unicorn • Санкт-Петербург

До 350 000 ₽

Системный аналитик

ЦИФРА

До 270 000 ₽

Настройка сервера

18 апр. 2024, в 21:56

2000 руб./за проект

Помощь с водпресс

18 апр. 2024, в 21:00

150 руб./за проект

Спарсить ссылки на все товары конкретного продавца в озон

18 апр. 2024, в 20:13

2000 руб./за проект

Так обычно пишут, чтобы было понятно, что ты способен вычислить с точностью до обыкновенной дроби, но не лезть в длинную. Дай подумать.
Mercury13, да, спасибо за ответ!
Разбираюсь)

Answer 1 · 2020-03-02 23:22:15

Про модули уже отвечено, я расскажу, как решать эту задачу быстрее, чем полным перебором.

Пусть общее количество карт - N.

Для простоты понимания, давайте забудем про колоду, просто карты раздаются как-то в 2 кучки по N/2 карт. Это пригодится попозже. Удобнее не вероятность считать, а количество способов раздать карты. Потом надо будет поделить количество хороших способов на все способы.

Сразу комбинаторно подсчитаем, сколько всего способов есть. Это просто количество всех различных колод. Гуглите "перестановки с повторениями". Формула будет такой:
N!/ a[1]! ... a[n]!
Раз мы на это число в конце будем делить, то сразу же считайте перевернутую формулу: подсчитайте факториал числа всех карт по модулю, обратите, умножьте на все маленькие факториалы.

Теперь самое главное, подсчитаем количество способов раздать карты так, что у всех поровну уникальных карт.
Динамическое программирование DP(k, t, i, j) - сколько способов раздать первые k типов карт так, что у первого игрока t карт всего, из них i уникальных, а у второго игрока j уникальных карт (при этом мы знаем, сколько у него всего карт - a[1]+...+a[k] - t).

База:

DP(0,0,0,0) = 1,
DP(0,*,*,*) = 0

Ответ:
sum {i=1..n} DP(n, N/2, i, i)

Пересчет:

DP(k,t,i,j) = sum{v=0..min(a[k],t)} DP(k-1, t-v, i - {v>0}, j-{v < a[k]}) * C(t, v) * C(a[1]+a[2]+...+a[k]-t, a[k]-v)

Тут надо объяснить: мы перебираем, сколько карт последнего типа досталось первому игроку: v. Это все разные колоды, поэтому их надо суммировать. Как бы убираем все карты этого последнего типа из рассмотрения. Что остается? То же самое ДП, но типов на 1 меньше, у первого игрока на v карт меньше и уникальные карты надо уменьшить на 1, если какому-то игроку хоть одна карта досталась. Но есть еще множители - это количество сочетаний. Эти самые v карт последнего типа могут быть на любом из t мест в колоде у первого игрока. Аналогично для второго игрока. Тут надо умножать, потому что любую колоду из предыдущего состояния ДП можно разбавить картами последнего типа в разных позициях и все эти способы дадут разные результирующие колоды. Надо домножить на оба сочетания, потому что мы независимо можем тасовать карты у первого и второго игрока.

Сочетания считаются факториалами С(n,k) = n!/ k! (n-k)!.
Я бы посоветовал предподсчитать все факториалы до 500 по модулю в массив, а так же обратные к ним.

Еще, если не будет влезать по памяти, обратите внимание, что в ДП достаточно хранить лишь 2 слоя по первому параметру. Т.е. надо места для 2*500*50*50 элементов, что для 4-х байтных значений будет занимать ~10mb памяти. Может даже long long можно хранить. Но тут надо переписать ДП снизу вверх, а не рекурсивно. Просто посмотрите, какие состояния куда плюсуются и с какими множителями. В этом случае вы будете не убирать карты последнего типа, а добавлять карты нового типа. Опять же, перебирайте сколько кому этих карт достанется. Надо только осторожно смотреть множители - С(сколько карт после добавления, сколько добавили).

Теперь прикинем на коленке сложность вычислений таким алгоритмом.
Само ДП имеет состояний 50*500*50*50 и пересчет 11 вариантов. Если все перемножить, получается что-то меньше 700 миллионов - в одну-две секунды должно влезать.

Полный перебор у вас, занимает что-то типа 11^50 - никогда не дождетесь на сколько нибудь не тривиальном тесте.

Answer 2 · 2020-03-01 17:48:06

Подобный вывод используется, чтобы было понятно, что вы способны, если нужно, вычислить с точностью до обыкновенной дроби, но в длинную арифметику (а дроби бывают длинные) не лезть. Ибо реализации длинной арифметики различаются по эффективности от ЯП к ЯП, а в некоторых вообще нет штатной (внешние библиотеки в олимпиадном программировании запрещены).

Числа P и Q высчитываем с точностью до остатка от деления на Z := 10⁹+ 7.

Авторы обещают, что Q mod Z ≠ 0. Z — простое. Тогда НОД(Q mod Z, Z) = 1. Так называемый расширенный алгоритм Евклида (гуглите!) позволяет подобрать такие числа, чтобы m(Q mod Z) + nZ = 1.

Ваша задача — вывести ((P mod Z) · m) mod Z. Специально указал дважды mod Z: первое у вас будет при работе с числом P, второе — при генерации вывода.

Почему так? Возьмём вместо здоровенного Z цифру поменьше, 17. Если у вас получился результат 100/400, при расчётах выйдет цифра 15/9, и 9·2+17·(−1) = 1, и ваша задача — вывести (15·2) mod 17 = 13.

Если же у вас получилось, например, 35/140, при расчётах получается 1/4, 1·(−4)+17·1 = 1, и вы должны вывести (1·(−4)) mod 17 = 13. То есть: независимо от того, насколько сократимая дробь у вас получилась, вы получите один и тот же результат. Тут надо уточнить: там, где возможен отрицательный числитель, нужен не обычный % из Си++, а (a % Z; если получилось отрицательное — добавь Z).

Ну а арифметических переполнений просто не допускайте, Z = 10⁹ + 7 позволяет умножать в типе long long и не уходить в переполнение.

UPD. То, что Z — простое, даёт несколько выгод. Часто результат бывает круглый, и простота требует честно считать остаток, а не угадывать. Ну и побочек меньше.

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

Войдите, чтобы написать ответ

Минуточку внимания

Войдите на сайт