反射容斥

あとどれくらいの距離を
月へ歩いたら
あとどれくらいの
寒い夜を重ねたら
あとどれくらいの
さよならを流したら
まぶたの奥の泉が枯れ果てるとか
千年後もきっと続くだろう
そう思ってた空洞を
満たしてあふれてしまうほどの
この気持ちはなんだ？
新しい風を
春は運んでくれるだろう
あぁ 風が吹くのが
きっと還る場所なんだろう
変わらないでしょう
夏の暑さも金魚も
花火が消えたら
星を夜通し数えよう
色褪せる木々
凍てつく指先
重ねた日々の灯火
降り積もる雪に埋もれないような
消えない跡を残しに
紙切れ一枚
手を伸ばしたドア
たった一言の「はい」や
ちっぽけな石ころ
そんなもので簡単に変わる未来は
単純だよ
毎朝の「おはよう」
映画みたいに青い夏の海を見て
遠いところで居場所を知り
今と今を重ねてく
フィルムのように
何回も撮り直しだ
色褪せるより 彩るより
君のいる景色が濃いな
直感でも咄嗟でもいい
そう思ったんだ ただ迷いなく
信じてもいいかと訊かれた
たったそれだけの問いだ
考えてるんだ どんな時も
あの声がつきまといながら
押してる ずっと背中を
そうか この気持ちが恋だ
単純だよ
毎朝の「おはよう」
映画みたいに青い夏の海を見て
遠いところで居場所を知り
今と今を重ねてく
フィルムのように
何回も撮り直しだ
色褪せるより 彩るより
君のいる景色が濃いな
千年前の灯火に
伸ばした二本の指が
千年後もずっと向こうで
輝いてるといいな
「信じてもいい」そう聞こえた
まんまるな月 仰いだ
照らしてた いつの世も
そうか この気持ちが恋だ

为什么 这个 有这么大阅读量。你们都是猫娘吗

设 \(P(a,b)\) 表示从 \((0,0)\) 到 \((a,b)\) 的方案数，即 \(=\dbinom{a+b}a\)

考虑一条线时：从 \((0,0)\) 走到 \((n,m)\)，不碰到 \(y=x+b\)。

卡特兰数，将 \((n,m)\) 按 \(y=x+b\) 翻转至 \((m-b,n+b)\)，发现触碰线的和从 \((0,0)\) 到 \((m-b,n+b)\) 一一对应，所以方案数就是 \(P(n,m)-P(m-b,n+b)\)

考虑多条线：

首先，对于在同一方向的两条线，显然只有近的一条有意义，对于在起点终点之间的，显然存在的话答案就是 \(0\)。

因此，只需要考虑其上下各有一条线即可。

设其为 \(y=x+a\) 和 \(y=x+b\)，在没有歧义的情况下简记为 \(a,b\)

有 \(simple\) 想法 \(ans=P(n,m) - \text{碰到 a} - \text{碰到 b} + \text{碰到 a 和 b}\)

考虑如何计算碰到 \(a\) 和 \(b\) 的。

考虑先碰到 \(a\) 在碰到 \(b\)，记为 \(ab\)，发现其相当于先按照 \(a\) 反射，在将反射后的点按照 \(b\) 反射。

类似的 \(ba\) 就是先 \(b\) 反射在 \(a\)反射，\(aba\) 就是先 \(a\) 反射在 \(b\) 反射在 \(a\) 反射。

有的做法要一起反射直线，但其实没必要，容易发现只按照最开始的直线反射点也是一样的，并且会好写。

总结一下，将 \(simple\) 补全：\(ans=P(n,m)-a-b+ab+ba-aba-bab...\)

例题 P3266 [JLOI2015] 骗我呢

首先发现每行只能空 \(1\) 个数，考虑设 \(dp_{i,j}\) 表示第 \(i\) 行没填 \(j\) 的方案数。

有显然转移：\(dp_{i,j}=\sum\limits_{i=0}^{j+1} dp_{i-1,k}\)

可以转化 \(\sum\limits_{i=0}^{j+1} dp_{i-1,k}=(\sum\limits_{i=0}^j dp_{i-1,k})+dp_{i-1,j+1}=dp_{i,j-1}+dp_{i-1,j+1}\)

但其实上面的式子就可以转化了，先依次向正推一个，将 \(j+1\) 产生的向左指的变成向上指的。 懒得放图了，QwQ

将左上指的变成左指，就和转化后推一个是一样的了。

加两条线就是板子。