AT2390 Games on DAG 题意 \(n\) 个点 \(m\) 条边的 DAG，每条边 \((u,v)\) 有 \(u<v\)。\(1,2\) 号点各一个石头，Alice 和 Bob 轮流每次沿边移动一个石头，不能动者输。求所有连边子集中先手胜的情况。两个石头可以重合。\(n\leq 15\)。 思路 发现对于两个石头的 SG 函数是独立的，输者两个石头 SG 函...

P2490 [SDOI2011]黑白棋 题意 一个 \(1*n\) 的棋盘上，A 可以移动白色棋子，B 可以移动黑色的棋子，其中白色不能往左，黑色不能往右。他们每次操作可以移动 1 到 \(d\) 个棋子。 每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。 思路 显然可以将题意转化为一种 K-Nim 游戏，即在 \(\frac...

斐波那契数列 \(F(0)=F(1)=1\) 或 \(F(1)=F(2)=1\)，\(F(i)=F(i-1)+F(i-2)\). 广义斐波那契数列在转移时有系数且首两项给定。 求法 注意到斐波那契数列的转移为一个矩阵乘 \[ \begin{bmatrix}F(i)&F(i-1)\end{bmatrix} \begin{bmatrix} 1&1\\ 1&...