洛谷P3750 分手是祝願

2022-09-23 01:32:03 字數 1486 閱讀 5557

b 君在玩一個遊戲,這個遊戲由 \(n\) 個燈和 \(n\) 個開關組成,給定這 \(n\) 個燈的初始狀態,下標為從 \(1\) 到 \(n\) 的正整數。

每個燈有兩個狀態亮和滅,我們用 \(1\) 來表示這個燈是亮的,用 \(0\) 表示這個燈是滅的,遊戲的目標是使所有燈都滅掉。

但是當操作第 \(i\) 個開關時,所有編號為 \(i\) 的約數(包括 \(1\) 和 \(i\))的燈的狀態都會被改變,即從亮變成滅,或者是從滅變成亮。

b 君發現這個遊戲很難,於是想到了這樣的一個策略,每次等概率隨機操作一個開關,直到所有燈都滅掉。

這個策略需要的操作次數很多,b 君想到這樣的一個優化。如果當前局面,可以通過操作小於等於 \(k\) 個開關使所有燈都滅掉,那麼他將不再隨機,直接選擇操作次數最小的操作方法(這個策略顯然小於等於 \(k\) 步)操作這些開關。

b 君想知道按照這個策略(也就是先隨機操作,最後小於等於 \(k\) 步,使用操作次數最小的操作方法)的操作次數的期望。

這個期望可能很大,但是 b 君發現這個期望乘以 \(n\) 的階乘一定是整數,所以他只需要知道這個整數對 \(100003\) 取模之後的結果。

\(1 \leq n \leq 100000, 0 \leq k \leq n\)

首先發現假設燈 \(i+1\sim n\) 全部滅掉,此時要滅掉 \(1\sim i\) 的燈,那麼必然需要動第 \(i\) 個開關,否則無法熄滅第 \(i\) 盞燈。

所以我們可以從 \(n\) 列舉到 \(1\),並計算有多少燈是一定要動開關的,那麼容易發現能滅掉所有燈的唯一方案必然是恰好動這些開關奇數次,並恰好動其他開關偶數次。

設 \(f[i]\) 表示從 \(i+1\) 盞必須動其開關的燈變成 \(i\) 盞必須動開關的燈的期望步數。那麼有 \(\frac\) 的概率選到必須關的燈,而如果沒有選到必須關的燈,那麼期望步數為 \((1+f[i+1]+f[i])\),所以有

\[f[i]=\frac+(1-\frac)(1+f[i+1]+f[i])

\]移項得

\[f[i]=1+\frac

\]計算出 \(f\),分兩種情況(假設有 \(m\) 盞燈必須動開關):

注意最終答案要乘上 \(n!\)。時間複雜度 \(o(n)\)。

#include using namespace std;

typedef long long ll;

const int n=100010,mod=100003;

int n,m,k,a[n];

ll ans,fac,f[n];

ll fpow(ll x,int k)

int main()

} if (m<=k) return printf("%lld",fac*m%mod),0;

f[n]=1ll;

for (int i=n-1;i>=k;i--)

printf("%lld",(ans+k)*fac%mod);

return 0;

}

Luogu P3750分手是祝願(期望DP)

題目連結 這題好喵啊 設f i 是最少用i次才能全關上轉移到最少用i 1次才能全關上燈的期望值,那麼n個燈裡有i個是正確的,剩下的都是不正確的 因此期望是 f i frac frac 然後我們把初始狀態最少用多少次才能關掉求出來 dp一遍,最後統計答案。 include include includ...

題解 洛谷P1562 還是N皇后

原題 洛谷p1562 這個題的原理和8皇后的原理是一模一樣的,就是必須要用n個皇后把每一個行填滿,同時滿足每一列,每一行,每一條對角線只有一個棋子。但如果按照原來的方法暴打的話只有60分 優化親測無效 所以這個時候,我們可以用二進位制來表示一波狀態 可以類比狀態壓縮的二進位制 。從上面的條件來看,我們需...

洛谷 P2580 於是他錯誤的點名開始了

xs中學化學競賽組教練是一個酷愛爐石的人。 他會一邊搓爐石一邊點名以至於有一天他連續點到了某個同學兩次,然後正好被路過的校長髮現了然後就是一...