先備知識 : 動態規劃 , 模逆元

先從暴力方法開始考慮，遞迴枚舉所有組合，每個數字都有選或不選，時間複雜度$O(2^N)$。

顯然這時間在$N=3000$時不可能通過，但是選跟不選這好像在哪見過，不就是背包問題嗎。

定義$f(i,j)$為選擇完前$i$個數字後$\mod P$等於$j$的方法數。

不過轉移似乎有點問題了，如果選擇$x_i$要從$frac{j}{x_i}$轉移，但$\mod$過要怎麼除法?

所以需要模逆元，在不$\mod$時，$\div x$等價$\times x^{-1}$，$x^{-1}$的意義是$x\times x^{-1}=1$，那在$\mod P$的情況下也是要找到$x\times x^{-1} \equiv 1\pmod P$。

$P$是質數的時候，可以根據費馬小定理 : $x^{P-1} \equvi 1 \pmod P$，可以寫成 $ x \times x^{P-2} \equiv 1 \pmod P$，所以$\mod P$時$x^{-1}$就會是$x^{P-2} \bmod P$，用快速冪計算時間複雜度為$O(log P)$。

對於這題這樣就夠了，所以轉移式$f(i,j)=f(i-1,j)+f(i-1,j*x_i^{-1})$。

時間複雜度 : 狀態數有$N\times P$個，轉移時需要快速冪求模逆元，總複雜度O(NP log P)，欸會TLE欸。

如果在程式一開始先預處理$1~P$的模逆然後存起來，轉移時就不用快速冪了，時間複雜度O(NP)，快樂AC。

code : https://github.com/kzzz-jpg/CP/blob/main/cpp/cchs/a138.cpp

先備知識 : 動態規劃 , 模逆元

先從暴力方法開始考慮，遞迴枚舉所有組合，每個數字都有選或不選，時間複雜度$O(2^N)$。

顯然這時間在$N=3000$時不可能通過，但是選跟不選這好像在哪見過，不就是背包問題嗎。

定義$f(i,j)$為選擇完前$i$個數字後$\mod P$等於$j$的方法數。

不過轉移似乎有點問題了，如果選擇$x_i$要從$frac{j}{x_i}$轉移，但$\mod$過要怎麼除法?

所以需要模逆元，在不$\mod$時，$\div x$等價$\times x^{-1}$，$x^{-1}$的意義是$x\times x^{-1}=1$，那在$\mod P$的情況下也是要找到$x\times x^{-1} \equiv 1\pmod P$。

$P$是質數的時候，可以根據費馬小定理 : $x^{P-1} \equvi 1 \pmod P$，可以寫成 $ x \times x^{P-2} \equiv 1 \pmod P$，所以$\mod P$時$x^{-1}$就會是$x^{P-2} \bmod P$，用快速冪計算時間複雜度為$O(log P)$。

對於這題這樣就夠了，所以轉移式$f(i,j)=f(i-1,j)+f(i-1,j*x_i^{-1})$。

時間複雜度 : 狀態數有$N\times P$個，轉移時需要快速冪求模逆元，總複雜度O(NP log P)，欸會TLE欸。

如果在程式一開始先預處理$1~P$的模逆然後存起來，轉移時就不用快速冪了，時間複雜度O(NP)，快樂AC。

code : https://github.com/kzzz-jpg/CP/blob/main/cpp/cchs/a138.cpp

ㄚ latex爛了

先備知識 : 動態規劃 , 模逆元

先從暴力方法開始考慮，遞迴枚舉所有組合，每個數字都有選或不選，時間複雜度$O(2^N)$。

顯然這時間在$N=3000$時不可能通過，但是選跟不選這好像在哪見過，不就是背包問題嗎。

定義$f(i,j)$為選擇完前$i$個數字後$\mod P$等於$j$的方法數。

不過轉移似乎有點問題了，如果選擇$x_i$要從$frac{j}{x_i}$轉移，但$\mod{}$過要怎麼除法?

所以需要模逆元，在不$\mod{}$時，$\div x$等價$\times x^{-1}$，$x^{-1}$的意義是$x\times x^{-1}=1$，那在$\mod P$的情況下也是要找到$x\times x^{-1} \equiv 1\pmod P$。

$P$是質數的時候，可以根據費馬小定理 : $x^{P-1} \equiv 1 \pmod P$，可以寫成 $ x \times x^{P-2} \equiv 1 \pmod P$，所以$\mod P$時$x^{-1}$就會是$x^{P-2} \bmod P$，用快速冪計算時間複雜度為$O(log P)$。

對於這題這樣就夠了，所以轉移式$f(i,j)=f(i-1,j)+f(i-1,j*x_i^{-1})$。

時間複雜度 : 狀態數有$N\times P$個，轉移時需要快速冪求模逆元，總複雜度O(NP log P)，欸會TLE欸。

如果在程式一開始先預處理$1~P$的模逆然後存起來，轉移時就不用快速冪了，時間複雜度O(NP)，快樂AC。

code : https://github.com/kzzz-jpg/CP/blob/main/cpp/cchs/a138.cpp

與其在$f(i,\ ...)$的時候找$f(i-1,\ ...)$，不如改成在$f(i,\ ...)$的時候更新$f(i+1,\ ...)$，就不用模逆元了

dp[0][ array[0] ] = 1
for i in 0..n-1:
    dp[ i+1 ] = copy(dp[i])
    for j in 0..P:
        dp[ i+1 ][ j * array[i] % P ] += dp[i][j]
answer: dp[n][1] % P

先備知識 : 動態規劃 , 模逆元

先從暴力方法開始考慮，遞迴枚舉所有組合，每個數字都有選或不選，時間複雜度$O(2^N)$。

顯然這時間在$N=3000$時不可能通過，但是選跟不選這好像在哪見過，不就是背包問題嗎。

定義$f(i,j)$為選擇完前$i$個數字後$\mod P$等於$j$的方法數。

不過轉移似乎有點問題了，如果選擇$x_i$要從$frac{j}{x_i}$轉移，但$\mod{}$過要怎麼除法?

所以需要模逆元，在不$\mod{}$時，$\div x$等價$\times x^{-1}$，$x^{-1}$的意義是$x\times x^{-1}=1$，那在$\mod P$的情況下也是要找到$x\times x^{-1} \equiv 1\pmod P$。

$P$是質數的時候，可以根據費馬小定理 : $x^{P-1} \equiv 1 \pmod P$，可以寫成 $ x \times x^{P-2} \equiv 1 \pmod P$，所以$\mod P$時$x^{-1}$就會是$x^{P-2} \bmod P$，用快速冪計算時間複雜度為$O(log P)$。

對於這題這樣就夠了，所以轉移式$f(i,j)=f(i-1,j)+f(i-1,j*x_i^{-1})$。

時間複雜度 : 狀態數有$N\times P$個，轉移時需要快速冪求模逆元，總複雜度O(NP log P)，欸會TLE欸。

如果在程式一開始先預處理$1~P$的模逆然後存起來，轉移時就不用快速冪了，時間複雜度O(NP)，快樂AC。

code : https://github.com/kzzz-jpg/CP/blob/main/cpp/cchs/a138.cpp

與其在$f(i,\ ...)$的時候找$f(i-1,\ ...)$，不如改成在$f(i,\ ...)$的時候更新$f(i+1,\ ...)$，就不用模逆元了

dp[0][ array[0] ] = 1
for i in 0..n-1:
    dp[ i+1 ] = copy(dp[i])
    for j in 0..P:
        dp[ i+1 ][ j * array[i] % P ] += dp[i][j]
answer: dp[n][1] % P

打錯 是 dp[ i+1 ][ j * array[i+1] % P ] += dp[i][j]