題目名稱:AND OR XOR
題目敘述
對於非負整數的 $a,b$ ,定義一個二元運算子 $*$ 。
- $x * y = (A×(x$ $AND$ $y)+B×(x$ $OR$ $y)+C×(x$ $XOR$ $y))$ $mod$ $4$
長度為 $N$ 的數列 $X$ 如果滿足以下條件則被稱作 好的數列 。 - 每一項都由 $0,1,2,3$ 組成。
- $(…((X_1 * X_2) * X_3) * …) * X_N = (…((X_N * X_{N-1}) * X_{N-2}) * …) * X_1$ 成立。
求 好的數列 的個數,由於答案可能會很大,所以請取除以 $998244353 $的餘數後出。
想法
這個問題可以用dp來處理,雖然 $N=5000$ ,但是這題的複雜度不是 $O(N^2)$ 而是 $O(N×4^5)$ 。
首先可以定義三個數列$P,X,R$,$X$代表任意的 好的數列 ,然後滿足:
$1.$ $P_{i-1} * X_i = P_i$
$2.$ $R_i * X_i = R_{i-1}$
假設 $(…(( X_1 * X_2 ) * X_3 ) * … ) * X_N = Y$ ,接著窮舉 $Y$ 。
而若 $R_1 = P_N = Y$ ,則 $(…((X_1 * X_2) * X_3) * …) * X_N = (…((X_N * X_{N-1}) * X_{N-2}) * …) * X_1$ 成立。
於是可以定義狀態 $dp[i][j][k]$ 代表在位置 $i$ 時, $P_i=j$ 且 $R_i=k$ 有解。
因為 $P_1 * X_2 = P_2$ 且 $R_2 * X_2 = R_1$ ,且 $R_1 = Y$ ,然後可以列出初始狀態:
$ ∀ j*k=Y , dp[1][j][k] = 1。$
接著可以列出轉移 $dp[i][P_i][R_i] = \sum dp[i-1][P_{i-1}][R_{i-1}] ( P_{i-1} * X_{i}=P_{i} \quad and \quad R_{i} * X_{i}=R_{i-1} )$
因為 $P_{N-1} * X_N = P_N$ 且 $R_{N} * X_N = R_{N-1}$ ,且 $P_N = Y$ 。
所以最後需要檢查所有的 $P_{N-1} * R_{N-1} = Y$ ,把滿足條件的 $dp[N-1][P_{N-1}][R_{N-1}]$ 加起來就會是答案了。
程式碼
1 |
|