I used this formula answ = x * d^(n — 1) * f( d / x , n — 1 ), where f(x,y) = fact(x + y) / fact(x — 1).

First handle the $$$D=0$$$ corner case. Now we know that if $$$N \geq mod$$$, answer is $$$0$$$.

Let's look at $$$x * (x + d) * (x + 2d) * ... * (x + (n - 1) * d)$$$. We will get $$$d$$$ out of every bracket and get $$$d^n * \frac{x}{d} * (\frac{x}{d} + 1) * (\frac{x}{d} + 2) * ... * (\frac{x}{d} + n - 1)$$$. This is basically a product of consecutive numbers when having them moded.

To find this product fast, we can build a segment tree for products on {1, 2, 3, 4, ..., 2 * mod}. Another way is to do suffix and prefix products.

I think pC is a common problem in probability textbooks, so it may be easy for some people.

mango_lassi wow, amazing solution.

const int N = 2000;
bitset<N> left_wins[N];
bitset<N> right_wins[N];
bitset<N> wins[N];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i < n; ++i) {
		string str;
		cin >> str;
		for (int j = 0; j < i; ++j) {
			if (str[j] == '1') wins[i][j] = 1;
			else wins[j][i] = 1;
		}
	}
	for (int b = 0; b < n; ++b) {
		right_wins[b][b] = 1;
		left_wins[b][b] = 1;
		for (int a = b-1; a >= 0; --a) {
			bitset<N> mask;

			mask = wins[b] & left_wins[a] & right_wins[b-1];
			if (mask.count() > 0) left_wins[a][b] = 1;
			mask = wins[a] & left_wins[a+1] & right_wins[b];
			if (mask.count() > 0) right_wins[b][a] = 1;
		}
	}

	bitset<N> res = left_wins[0] & right_wins[n-1];
	cout << res.count() << '\n';
}

haha Mathcoder ?

And, what is "the expected number of games". Number of games with a possibilitie of min 0.5 of reaching n? And, how can "the expected number of games" be a fraction?

We can reduce the problem to one with $$$C = 0$$$. Just normalize $$$A$$$ and $$$B$$$, so that $$$A + B = 1$$$, and multiply the answer by $$$\frac{1}{1 - C}$$$.

I will denote by $$$a$$$, $$$b$$$ and $$$c$$$ the probabilities and not the percentages.

First find the expected number of turns to have a non-draw outcome. It is equal to $$$\frac{1}{1-c}$$$ and I will denote it as $$$d$$$.

Now let's fix the number of wins of the first player, assuming the second will win. Let this number be $$$x$$$. Then we choose which of the games will be wins for the first player. This means we will have to add to the answer: $$$d * (n + x) * \binom{n + x - 1}{x} * (\frac{a}{a + b})^x * (\frac{b}{a + b})^n$$$.

We do the same if the first player wins.

Consider a straight tree like 1-2-3-4-5. We can notice that we have to assign ci values in increasing/decreasing order to attain the maximum value. The same thing applies to any tree. Considering 1 as the root and every path from 1 to a leaf node should be in decreasing order to attain the maximum value where our maximum value is the sum of all c[i]'s except the largest value. This is equivalent to every node in subtree should be less than or equal to the root node of the subtree. Sort all the subtrees by their sizes and assign them the values in increasing order of c[i]'s.

Yes, it's very similar. I haven't checked this TC task, sorry...