제출 #661077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
661077		lunchbox1	Chess Rush (CEOI20_chessrush)	C++17	100 / 100	300 ms	8268 KiB

chessrush

// 100p
#include <array>
#include <iostream>
#include <cmath>
using namespace std;

const int N = 1000, P = 1e9 + 7;

int solve(int m, int j1, int i2, int j2) {
 int d = i2 / (m - 1);
 if ((d % 2 == 0 && i2 % (m - 1) > abs(j1 - j2)) || (d % 2 == 1 && i2 % (m - 1) > abs(m - 1 - j1 - j2)))
  d++;
 return d + 1;
}

int m;

struct mat {
 array<array<int, N>, N> f;

 void identity() {
  for (int i = 0; i < m; i++) {
   fill(f[i].begin(), f[i].end(), 0);
   f[i][i] = 1;
  }
 }
 void square() {
  static array<array<int, N>, N> g;
  for (int i = 0; i < m; i++)
   fill(g[i].begin(), g[i].end(), 0);
  for (int j = 0; j < m; j++)
   for (int i = 0; i < m; i++)
    g[0][j] = (g[0][j] + (long long) f[0][i] * f[i][j]) % P;
  for (int i = 0; i < m; i++)
   g[i][0] = g[0][i];
  for (int i = 1; i < m; i++)
   for (int j = 1; i + j < m; j++)
    g[i][j] = (g[i - 1][j - 1] + g[0][i + j]) % P;
  for (int i = 0; i < m; i++)
   for (int j = 0; i + j < m; j++)
    g[m - 1 - i][m - 1 - j] = g[i][j];
  f = g;
 }
 void once() {
  static array<int, N> g;
  for (int i = 0; i < m; i++) {
   g = f[i];
   for (int j = 0; j < m; j++) {
    f[i][j] = g[j];
    if (j > 0)
     f[i][j] = (f[i][j] + g[j - 1]) % P;
    if (j < m - 1)
     f[i][j] = (f[i][j] + g[j + 1]) % P;
   }
  }
 }
 void power(int k) {
  if (k == 0)
   identity();
  else {
   power(k / 2);
   square();
   if (k & 1)
    once();
  }
 }
} dp;

int v[N + 1];

int ch(int n, int k) {
 return k == 0 ? 1 : 1LL * ch(n - 1, k - 1) * n % P * v[k] % P;
}

int main() {
 ios::sync_with_stdio(0), cin.tie(0);
 v[1] = 1;
 for (int i = 2; i <= N; i++)
  v[i] = 1LL * v[i - P % i] * (P / i + 1) % P;
 int n, q;
 cin >> n >> m >> q;
 dp.power(n - 1);
 while (q--) {
  char t;
  int j1, jn;
  cin >> t >> j1 >> jn, j1--, jn--;
  if (t == 'P') {
   if (j1 == jn)
    cout << n - 1 << ' ' << 1 << '\n';
   else
    cout << 0 << ' ' << 0 << '\n';
  } else if (t == 'R') {
   if (j1 == jn)
    cout << 1 << ' ' << 1 << '\n';
   else
    cout << 2 << ' ' << 2 << '\n';
  } else if (t == 'Q') {
   if (j1 == jn || (n == m && ((j1 == 0 && jn == m - 1) || (j1 == m - 1 && jn == 0))))
    cout << 1 << ' ' << 1 << '\n';
   else {
    int c = 4; // ll, ll, dl, dl
    if (n == m && (j1 == 0 || j1 == m - 1 || jn == 0 || jn == m - 1)) // ld
     c++;
    if ((0 + j1) % 2 == (n - 1 + jn) % 2) { // dd
     int x, y;
     x = ((0 + j1) + (n - 1 - jn)) / 2, y = ((0 + j1) - (n - 1 - jn)) / 2;
     c += x >= 0 && x < n && y >= 0 && y < m;
     x = ((0 - j1) + (n - 1 - jn)) / 2, y = ((n - 1 - jn) - (0 - j1)) / 2;
     c += x >= 0 && x < n && y >= 0 && y < m;
    }
    cout << 2 << ' ' << c << '\n';
   }
  } else if (t == 'B') {
   if ((0 + j1) % 2 != (n - 1 + jn) % 2)
    cout << 0 << ' ' << 0 << '\n';
   else if (((j1 == 0 && jn == 0) || (j1 == m - 1 && jn == m - 1)) && ((n - 1) % ((m - 1) * 2) == 0))
    cout << (n - 1) / (m - 1) << ' ' << 1 << '\n';
   else if (((j1 == 0 && jn == m - 1) || (j1 == m - 1 && jn == 0)) && (((n - 1) % ((m - 1) * 2)) == m - 1))
    cout << (n - 1) / (m - 1) << ' ' << 1 << '\n';
   else {
    int d = solve(m, j1, n - 1, jn), c = 0, x, y;
    if (d % 2) {
     if ((x = n - 1 + jn) <= (y = (m - 1) * (d - 1) + j1 + 0))
      c = (c + ch((y - x) / 2 + d - 2, (y - x) / 2)) % P;
     if ((x = n - 1 - jn) <= (y = (m - 1) * (d - 1) + m - 1 - j1 - (m - 1)))
      c = (c + ch((y - x) / 2 + d - 2, (y - x) / 2)) % P;
    } else {
     if ((x = n - 1 + jn) <= (y = (m - 1) * (d - 1) + m - 1 - j1 + 0))
      c = (c + ch((y - x) / 2 + d - 2, (y - x) / 2)) % P;
     if ((x = n - 1 - jn) <= (y = (m - 1) * (d - 1) + j1 - (m - 1)))
      c = (c + ch((y - x) / 2 + d - 2, (y - x) / 2)) % P;
    }
    cout << d << ' ' << c << '\n';
   }
  } else
   cout << n - 1 << ' ' << dp.f[j1][jn] << '\n';
 }
 return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 22 / 22
• Subtask 5: 5 / 5
• Subtask 6: 8 / 8
• Subtask 7: 15 / 15
• Subtask 8: 20 / 20
• Subtask 9: 7 / 7