CS Academy Partial Ladder Graph - akusyouninのブログ

リンク : https://csacademy.com/contest/archive/task/partial_ladder_graph/statement/

問題概要

N2頂点とN+2(N-1)辺のグラフが与えられる。1<=i<=N-1 の頂点iはi+1同士を結んでいる。N<=i<=2N-1も同様である。また、1<=i<=N-1の頂点iと頂点i+(N-1)は結ばれている。このとき、辺を削除しても連結である、辺の集合の通り数を求めよ。

解説

Nが1から2に変わったときに、辺1-2、辺2-4、辺3-4の3辺のみしか変わらないため、一つ前の遷移が使えるのではという考察と、N<= ${10}^{18}$ から繰り返し二乗法か行列累乗が浮かぶ。そこでdp[i][0]をi番目までで、これからの遷移によっては連結になりうる通り数(現在は連結でない)とし、dp[i][1]をi番目までで、現在連結である通り数とする。そうすると、公式解説の図のように考えると、
dp[i+1][0]=dp[i][0]+dp[i][1]×2
dp[i+1][1]=dp[i][0]+dp[i][1]×4
となる。普通に計算してしまうとTLEである。この形なら行列累乗ができるため、O(log N)でこの問題が解ける。

LL n;
int main() {
    cin >> n;
    n--;
    matrix<LL>mat(2), A(2,1);
    A.mat[0][0] = 1;
    A.mat[1][0] = 1;
    mat.mat[0][0] = 1;
    mat.mat[0][1] = 2;
    mat.mat[1][0] = 1;
    mat.mat[1][1] = 4;
    matrix<LL>ANS(mat.Pow(n)*A);
    cout << ANS.mat[1][0] << endl;

    return 0;
}