4872: [Shoi2017]分手是祝愿

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

Description

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

Input

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

Output

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

Sample Input

4 0

0 0 1 1

Sample Output

512

HINT

Source

黑吉遼滬冀晉六省聯(lián)考

?

直接概率dp懶得寫式子了

應該很久以前就做過這題但是一直沒有在BZOJ交

?

1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 const int MAXN = 110000; 6 const int INF = 100003; 7 long long n, k; 8 long long f[MAXN], ans; 9 long long dp[MAXN]; 10 11 template <typename tn> void read (tn & a) { 12 tn x = 0, f = 1; 13 char c = getchar(); 14 while ( c < '0' || c > '9' ) { if (c == '-') f = -1; c = getchar(); } 15 while ( c >= '0' && c <= '9' ) { x = x * 10 + c - '0'; c = getchar(); } 16 a = f == 1 ? x : -x; 17 } 18 19 long long inv (long long x) { 20 if (x == 1) return 1; 21 return - ( inv(INF % x) * (INF / x) ) % INF; 22 } 23 24 int main() { 25 read(n); 26 read(k); 27 dp[n] = 1; 28 for (int i = n - 1; i > k; --i) { 29 dp[i] = 1 + (n - i) * (dp[i + 1] + 1) * inv(i); 30 dp[i] %= INF; 31 } 32 ans = 0; 33 for (int i = 1; i <= n; ++i) read(f[i]); 34 for (int i = n; i >= 1; --i) { 35 if (f[i]) { 36 ++ans; 37 for (int j = 1; j * j <= i; ++j) { 38 if (i % j == 0) { 39 if (j * j == i) { f[j] = 1 - f[j]; continue; } 40 f[j] = 1 - f[j]; 41 f[i / j] = 1 - f[i / j]; 42 } 43 } 44 } 45 } 46 long long an = min(ans, k); 47 for (int i = ans; i > k; --i) { 48 an += dp[i]; 49 an %= INF; 50 } 51 for (int i = 2; i <= n; ++i) { 52 an *= i; 53 an %= INF; 54 } 55 while (an < 0) an += INF; 56 an %= INF; 57 cout << an << "\n"; 58 return 0; 59 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/m-m-m/p/8951969.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。