排列
請問有多少個長度為 n n n 的排列 P P P 滿足 ∣ i ? P i ∣ ≤ 1 |i-P_i|\leq1 ∣i?Pi?∣≤1，答案對 998244353 998244353 998244353 取模，
設 f i f_i fi? 為確定了前 i i i 位的排列個數，那么第 i i i 個位置要不然填 i i i，要不然填 i ? 1 i-1 i?1，讓 i ? 1 i-1 i?1 個位置填 i i i，所以轉移為 f i = f i ? 1 + f i ? 2 f_i = f_{i-1}+f_{i-2} fi?=fi?1?+fi?2?，矩陣加速一下即可，
游走
顯然最深的那條鏈放最后走，且如果鏈能走完，那么最后一定停在鏈的末端，而你從根結點出發，走 x x x 個點再回到根節點只需要 2 × x 2 \times x 2×x 步，所以討論一下就行，
顏色
做過原題
區間
給一個長度為 n n n 的序列和 m m m 個有編號的區間，詢問有多少種合法的放置方案使得每個格子上覆寫的區間數都不超過 t t t，方案數對 998244353 998244353 998244353 質數取模，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/42386.html
標籤：java