解法: 行列冪乗
これも遷移が線形になるので，行列冪で解ける． 状態を \(2^{K}\) で持っておき， 次数\(2^{K}\)の行列を考える．
まず\(N\)が小さい場合で考えてみる． DP による全探索をすると， 左から \(i\) 列目を決めるときは， \(i-1\) 列目の配置によってのみ影響を受ける． 実際，\(i-1\) 列目を敷き詰めるとき， \(i\) 列目においてどの場所にはみ出したかで， \(i\) 列目の敷き詰め方が決まる．
(\(k \in K\) 列目においてはみ出しているか) \(\in 2\) と考えれば， 状態が \(2^{K}\) となる． これは 2進数で考えるとよい． 例えば\(K=4\)のとき，
xy
1 **
0 *
0 *
1 **
1 **
0 *
0 *
1 **
の様な形になる．\(x\)が今の行，\(y\)が次の行． 次の行にはみ出している部分だけ \(1\)， それ以外は \(0\) を割り当ててて， 2進数 \(1001\) を対応させる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll k; cin >> k;
ll n;
cin >> n;
if(k == 2){
{1,0,0,1},
{0,0,1,0},
{0,1,0,0},
{1,0,0,0}
});
{1,0,0,0}
});
cout << (ini*a2.pow(n)).get(0,0).val() << endl;
}else if(k == 3){
{0,1,0,0, 1,0,0,1},
{1,0,0,0, 0,0,1,0},
{0,0,0,0, 0,1,0,0},
{0,0,0,0, 1,0,0,0},
{1,0,0,1, 0,0,0,0},
{0,0,1,0, 0,0,0,0},
{0,1,0,0, 0,0,0,0},
{1,0,0,0, 0,0,0,0},
});
{1,0,0,0, 0,0,0,0}
});
cout << (ini*a3.pow(n)).get(0,0).val() << endl;
}else if(k == 4){
{1,0,0,1, 0,0,0,0, 0,1,0,0, 1,0,0,1},
{0,0,1,0, 0,0,0,0, 1,0,0,0, 0,0,1,0},
{0,1,0,0, 0,0,0,0, 0,0,0,0, 0,1,0,0},
{1,0,0,0, 0,0,0,0, 0,0,0,0, 1,0,0,0},
{0,0,0,0, 0,0,0,0, 1,0,0,1, 0,0,0,0},
{0,0,0,0, 0,0,0,0, 0,0,1,0, 0,0,0,0},
{0,0,0,0, 0,0,0,0, 0,1,0,0, 0,0,0,0},
{0,0,0,0, 0,0,0,0, 1,0,0,0, 0,0,0,0},
{0,1,0,0, 1,0,0,1, 0,0,0,0, 0,0,0,0},
{1,0,0,0, 0,0,1,0, 0,0,0,0, 0,0,0,0},
{0,0,0,0, 0,1,0,0, 0,0,0,0, 0,0,0,0},
{0,0,0,0, 1,0,0,0, 0,0,0,0, 0,0,0,0},
{1,0,0,1, 0,0,0,0, 0,0,0,0, 0,0,0,0},
{0,0,1,0, 0,0,0,0, 0,0,0,0, 0,0,0,0},
{0,1,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0},
{1,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0}
});
{1,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0}
});
cout << (ini*a4.pow(n)).get(0,0).val() << endl;
}
return 0;
}
