4872: [Shoi2017]分手是祝愿

Time Limit:?20 Sec??Memory Limit:?512 MB
Submit:?458??Solved:?299
[Submit][Status][Discuss]

Description

Zeit und Raum trennen dich und mich. 時空將你我分開。B 君在玩一個游戲，這個游戲由 n 個燈和 n 個開關組成，給定這 n 個燈的初始狀態，下標為 從 1 到 n 的正整數。每個燈有兩個狀態亮和滅，我們用 1 來表示這個燈是亮的，用 0 表示這個燈是滅的，游戲 的目標是使所有燈都滅掉。但是當操作第 i 個開關時，所有編號為 i 的約數（包括 1 和 i）的燈的狀態都會被 改變，即從亮變成滅，或者是從滅變成亮。B 君發現這個游戲很難，于是想到了這樣的一個策略，每次等概率隨機 操作一個開關，直到所有燈都滅掉。這個策略需要的操作次數很多， B 君想到這樣的一個優化。如果當前局面， 可以通過操作小于等于 k 個開關使所有燈都滅掉，那么他將不再隨機，直接選擇操作次數最小的操作方法（這個 策略顯然小于等于 k 步）操作這些開關。B 君想知道按照這個策略（也就是先隨機操作，最后小于等于 k 步，使 用操作次數最小的操作方法）的操作次數的期望。這個期望可能很大，但是 B 君發現這個期望乘以 n 的階乘一定 是整數，所以他只需要知道這個整數對 100003 取模之后的結果。

Input

第一行兩個整數 n, k。 接下來一行 n 個整數，每個整數是 0 或者 1，其中第 i 個整數表示第 i 個燈的初始情況。 1 ≤ n ≤ 100000, 0 ≤ k ≤ n；

Output

輸出一行，為操作次數的期望乘以 n 的階乘對 100003 取模之后的結果。

Sample Input

4 0
0 0 1 1

Sample Output

512

HINT

Source

黑吉遼滬冀晉六省聯考

首先一個狀態最少需要多少步是可以 O(N log N)算出來的，調和級數一下就好了。 而且我們可以發現，對于每一個狀態，用最小步數關掉所有燈的方案是唯一的，考慮從后向前掃描，是1就動否則不動，總是最優的。 然后我們就設 f[i] 為關掉所有燈的最小步數為i的期望答案。 顯然 當i<=k的時候，f[i]=i；其他情況，f[i] = (i/n) * f[i-1] + ((n-i)/n) * f[i+1] 。 為什么隨機的式子是長那個樣子的呢？ 前面已經證明了對于每一個狀態，最小步數關掉所有燈的方案是唯一的。 而又因為按燈的順序不影響答案，所以有(i/n)的幾率最短步數減少； 但如果沒有按最短路上的燈，首先最短步數不會減少，因為最短路唯一； 而且也不會不變，因為如果還按原來的套路按燈的話最后不會都滅； 那么按了不是最短方案的燈，會讓最短步數增加多少呢？ 只能是1，因為可以再按一步回去。 我們可以發現的是，f[n] = f[n-1] + 1。 通過這個向前推，可以推出形如f[i] = f[i-1] + h[i]的式子，并且h[i] = (n / i) (1 + h[i+1] * (n-i) / n) 。 然后就可以直接從前往后遞推了，對于i<=k,f[i] = i；否則, f[i] = f[i-1] + h[i] 。 然后就可以A了2333 #include<bits/stdc++.h> #define ll long long #define maxn 100005 #define ha 100003 using namespace std; int n,k,T,a[maxn],opt[maxn]; int f[maxn],jc=1,inv[maxn],h[maxn];inline int add(int x,int y){x+=y;return x>=ha?x-ha:x; }inline void init(){inv[1]=1;for(int i=2;i<ha;i++) inv[i]=-inv[ha%i]*(ll)(ha/i)%ha+ha; }int main(){init();scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%d",a+i),jc=jc*(ll)i%ha;for(int i=n;i;i--){for(int j=i<<1;j<=n;j+=i) a[i]^=opt[j];if(a[i]) opt[i]=1,T++;}f[0]=0;for(int i=1;i<=k;i++) f[i]=i;h[n]=1;for(int i=n-1;i;i--) h[i]=add(n*(ll)inv[i]%ha,h[i+1]*(ll)(n-i)%ha*(ll)inv[i]%ha);for(int i=k+1;i<=T;i++) f[i]=add(f[i-1],h[i]);printf("%d\n",f[T]*(ll)jc%ha);return 0; }

　　

轉載于:https://www.cnblogs.com/JYYHH/p/8521162.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的2017 [六省联考] T5 分手是祝愿的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。