If the given number is divisible by every number up to 5000, this will fail. To make it pass, we have to increase the upper limit.

Different tests (33-52) contain integers divisible by every prime up to 10⁷, and tests 33-34 are divisible by all primes from 2 to 833 947 simultaneously.

Thank you. Finally got AC with first 50 prime numbers bigger than 10⁹ + 7.

Is that all that you do? It seems that I can last for more then N turns this way

Suppose N = 2K — big enough
Queen=(1, 1);Knight = (K, N)
Turn1: Queen=(K, 1), Knight = (K+2, N — 1)
Turn2: Queen=(K, N — 1). Knight = (K + 1, N — 3)

Now I think you need 2N — 1 more turns to win And it will be even a bit more, if we move knight starting point to the left to (2,N) or so

(column first in all coordinates)

We used basically the same idea(go to the same row, then win in O(2 * halfwidth), but we needed additional bruteforce for first few turns because otherwise sometimes we needed N + 1 turns

H is the computation of a resultant (case t = xy in https://en.wikipedia.org/wiki/Resultant#Number_theory ), but general algorithms for computing resultants are not fast enough. It seems that an efficient algorithm is given in http://algo.inria.fr/flajolet/Publications/BoFlSaSc02.pdf (Corollary 4).

H:

Using this one can easily find the k-th coefficient of and then calculate .

B is similar to Jigsaw Puzzle from Moscow Subregional 2013.

We can solve it with dp by profile. State is:

1. column id

2. mask of colors in last column

3. list of possible masks (each mask: has 1 on position i if there is a horizontal pile from last column to next one in row i)

Yes, it looks like m * 2^n * 2^(2^n) states. But most of states are unreachable. And for n=6 there are about 1600 reachable states per column.

B. Checking if coloring is good can be done by dynamic programming on set of border points which are already colored. Dynamic programming of set of states reachable states of dynamic programming above on one layer works fast enough to pass or precalc (~1.2s in yandex context for me).

See code for more details. I think it's quite easy.

int n, m;
map<ull, int> dp[64];
map<ull, int> ndp[64];

void go(ll in_masks, int mask, int pos, int cnt, map<ull, int>& to, int bit) {
  ll res_masks = 0;
  for (int i = 0; i < (1 << n); i++) {
    if (!(in_masks & (1ULL << i))) {
      continue;
    }
    if (!(i & (1 << pos))) {
      if (((mask >> pos) & 1) != bit) {
        int ni = i | (1 << pos);
        res_masks |= (1ULL << ni);
      }
    } else {
      {
        int ni = i & ~(1 << pos);
        res_masks |= (1ULL << ni);
      }
      if (pos && !(i & (1 << (pos - 1))) && ((mask >> (pos - 1)) & 1) != bit) {
        int ni = i | (1 << (pos - 1)) | (1 << pos);
        res_masks |= (1ULL << ni);
      }
    }
  }
  if (res_masks && cnt) {
    add(to[res_masks], cnt);
  }
}

int main() {
#ifdef LOCAL
  freopen("b.in", "r", stdin);
  freopen("b.out", "w", stdout);
#endif

  scanf("%d%d", &n, &m);
  dp[0][1ULL << ((1 << n) - 1)] = 1;

  for (int j = 0; j < m; j++) {
    for (int i = 0; i < n; i++) {
      for (int mask = 0; mask < (1 << n); mask++) {
        for (auto x : dp[mask]) {
          go(x.first, mask, i, x.second, ndp[mask & ~(1 << i)], 0);
          go(x.first, mask, i, x.second, ndp[mask | (1 << i)], 1);
        }
      }

      for (int mask = 0; mask < (1 << n); mask++) {
        dp[mask].swap(ndp[mask]);
        ndp[mask].clear();
      }
    }
  }

  int ans = 0;
  for (int mask = 0; mask < (1 << n); mask++) {
    for (auto x : dp[mask]) {
      if (x.first & (1ULL << ((1 << n) - 1))) {
        add(ans, x.second);
      }
    }
  }

  printf("%d\n", ans);

  return 0;
}

It took me 140 minutes to solve 7 tasks and more than 3 hours to solve H, I feel this is an overkill, but anyway...

We use Newton's identities. Check the definitions of e_i and p_i there.

Let A = {a_i}, B = {b_i}, C = {a_ib_j}. We are given the values of e_i(A) and e_i(B), and we want to get e_i(C).

1. From e_i(A), compute p_i(A).
2. From e_i(B), compute p_i(B).
3. Compute p_i(C). This is quite easy because p_i(C) = p_i(A)p_i(B).
4. From p_i(C), compute e_i(C).

Thus, the main challenge is the conversion between p_i and e_i.

Now, let's use Newton's identities. It says that the convolution of (0, p₁,  - p₂, p₃,  - p₄, p₅,  - p₆, ...) and (e₀, e₁, e₂, ...) is (0, e₁, 2e₂, 3e₃, 4e₄, ...). Let P(X) = 0 + p₁X - p₂X² + p₃X³ - p₄X⁴ + ... and E(X) = e₀ + e₁X + e₂X² + e₃X³ + .... We have P(X)E(X) = E'(X)X (Don't miss derivative sign).

The conversions between P and E can be done as follows:

• P(X) = E'(X)X × inverse(E(X)).
• P(X) / X = E'(X) / E(X) = (log(E(X)))', thus .

Computation of inverses: Link (Check problem E)

Computation of exponentiation: Link (Left part of Fig.1 is enough)

(I'm not quite sure why these computations with integrations/differentiations are valid.)

We solved H by Newton-Girard formulas and divide-and-conquer FFT.