点対称 [yukicoder No.557]

https://yukicoder.me/problems/no/557

解説放送

未定

解説

https://yukicoder.me/submissions/196785

N=1は別途答えておく。
何通りあるか確定させていくが、まず一番外側の数は0となってはいけないので「1869」の4通りある。
Nは奇数であれば中心の数ができる。中心の数になれるのは「180」の3通り。
あとの数は「18069」で埋めることができるが、回転の関係上、前半の数が決まると後半の数が決まるため、
前半の数の組み合わせ数のみ計算する。
これは奇数個であれば5^((N-1)/2)、偶数個であれば5^(N/2)
全てかければ答え。

typedef long long ll;
ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    if (N == 1) {
        printf("2\n");
        return;
    }

    mint ans = 4;
    N -= 2;
    if (N % 2 == 1) {
        ans *= 3;
        ans *= mint(5) ^ ((N - 1) / 2);
    } else ans *= mint(5) ^ (N / 2); 

    cout << ans << endl;
}