AtCoder AGC051-A Dodecagon 해설

문제.

질문 링크
1변의 길이가 1인 정사각형, 정삼각형을 이용하여 1변의 길이가 d인 정12변을 만드는 방법은 몇 가지가 있다.

해설

정12각의 내각은 150도이기 때문에 정점 부분은 반드시 정사각형과 정삼각형이 인접한 형식으로 사용해야 한다.①
따라서 어떤 정점에 주목할 때 정점 부분의 매립 방법은 다음과 같은 실선과 허선 두 가지가 있다.

또한 정12각의 변 부분에서 정사각형과 정삼각형이 서로 인접하면 30도의 간격이 생겨 정사각형과 정삼각형으로 메울 수 없다.따라서 변의 부분은 연속적으로 정사각형과 정삼각형이다.②
①②부터 어느 정점 부분의 매립 방법을 결정하면 다음과 같이 바깥쪽의 매립 방법을 확정한다.

그럼 안쪽에 12각이 나옵니다.바깥쪽 12각의 변의 길이는 d이기 때문에 안쪽 12각의 변의 길이는 d, d-1, d, d-1이다.네.
안쪽의 12변형도 ①②에 따라 바깥쪽에서 매립되므로 안쪽에는 12변형이 나타난다.이렇게 차례대로 계속하다.
만약에 귀착적으로 고려한다면 정12각 이외의 12각을 고려할 필요성이 생겼기 때문에 이곳의 일반 변의 길이는 a, b, a, b이다.의 12개 각의 구개수 f(a,b).
위의 그림을 참고하면 12개의 각의 안쪽 12개의 각의 변의 길이는 다음과 같다.

바깥쪽의 12사각형 접촉변에 평행: 평행변과 같은 길이

"외측 12개 삼각형의 정삼각형과 접촉하는 변"과 평행한 변: 평행한 변의 길이-1

외측 정점 부분의 충전 방법에 따라 정사각형과 a, b의 어느 쪽이 접촉하면 변화가 발생한다.
따라서 안쪽 12각의 변의 길이는 a-1, b, a-1, b이다.아니면, a, b-1, a, b-1.두 가지 있어요.
안쪽 12각의 매립 방법은 각각 f(a-1, b), f(a, b-1), f(a, b)=f(a-1, b)+f(a, b-1)이다.
신경 쓰이는 것은 a-1, b-1의 계산변의 길이가 0인 경우다.
이것은 정육각형이 아래의 그림에서 12개의 각의 안쪽에 나타나는 것을 나타낸다.이런 상황에서 이 정육각형의 충전 방법은 f(2,0)라고 볼 수 있다.

정육각형의 내각은 120도이기 때문에 정점 부분은 반드시 인접한 형식으로 정삼각형을 채워야 한다.이것과 ②부터 정육각형의 변과 접촉하는 부분은 모두 정삼각형으로만 채울 수 있다.
또 매립 안쪽에는 가장자리 길이가 1작은 정육각형이 나타난다.
역귀적으로 생각해 보면 정육각형의 매립 방법은 그림의 허선처럼 내부를 모두 정삼각형으로 채우는 것 하나밖에 없다는 것을 알 수 있다.
위에서 다음과 같은 점화 공식을 얻을 수 있다.
\newcommand{\arraystretch}{1.7}
f(a, b) =
\left\{
\begin{array}{rcl}
f(a-1, b) + f(a, b-1) & (a\gt 0\land b\gt 0)\\
1 & (a = 0\lor b = 0)
\end{array}
\right.
구한 답은 f(d,d)이다.솔직히 상술한 기록을 O(d^2)로 기록화했지만 이번 제한 d\leq10^6은 늦었다.
작은 a, b를 f(a, b)에 기입하면 다음과 같이 두 가지 계수를 쉽게 느낄 수 있는 표를 얻을 수 있다.

확실히 f(a,b)는'맨 왼쪽 위의 송어에서 오른쪽 또는 아래로 이동하여 송어(a,b)에 도착하는 경로'를 나타내는 개수로 이해할 수 있는데, 이 개수는{a+b}\mathrm{C}_a.
따라서 f(a,b)={a+b}\mathrm{C}_a와 단순화할 수 있다.{2d}\mathrm{C}_d.
마지막으로 회전 후 일치하는 물체를 같은 물체로 보고 계수해야 한다.12각형의 가장 바깥쪽 부분을 채우는 방법은 회전과 일치하는 두 가지가 있기 때문에 구분할 수 없으며 반드시 2로 나누어야 한다.

코드

#include <atcoder/all>

#include "iostream"

using namespace atcoder;
using namespace std;

// ※ 実際の問題では求める個数を 998244353 で割ったあまりの出力が求められている
using mint = modint998244353;

int main() {
  int D;
  cin >> D;

  mint res = 1;

  for (int i = 0; i < D; ++i) {
    res *= 2 * D - i;
  }

  for (int i = 1; i <= D; ++i) {
    res /= i;
  }

  res /= 2;

  cout << res.val() << "\n";
  return 0;
}

감상

고찰 부분은 매우 중요하고 결론은 매우 간단하며 매우 무감각하다.

참고 자료

공식 해설