反射容斥

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

為什么 這個 有這么大閱讀量。你們都是貓娘嗎

設 \(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

將左上指的變成左指，就和轉化后推一個是一樣的了。

加兩條線就是板子。