關燈游戲

金牌導航 期望-8

題目大意

有n盞燈，有些是亮的，有的是暗的，現在如果按一個位置的開關，那么是它因數的位置的燈都會改變開關情況，現在如果用k步不能直接關完，就隨機按，直到可以k步關完，就用最小的步數，問你期望步數

樣例輸入

4 0 0 0 1 1

樣例輸出

512

樣例輸入

5 0 1 0 1 1 1

樣例輸出

5120

數據范圍

$1?n?10^5,0?k?n$

解題思路

對于第n個燈，只有第n個開關可以控制它，那么第n個開關必須使第n個燈熄滅，熄滅后就不能再動了
對于前面的燈，后面的開關都不能動，所以只有當前開關可以控制當前燈，所以必須使其關閉
以此類推，對于每一個位置，都有其按或不按的選擇
記我們最優按sum次可以直接熄滅
可以從大到小暴力求要sum
設f_i為要再按i個開關時，當前開關按對的期望值
那么有:
$$f_i=\frac{i}{n}+\frac{n?i}{n}\times (1+f_{i+1}+f_i)$$
$\frac{i}{n}$是i個開關中按對一個的期望
$\frac{n?i}{n}\times (1+f_{i+1}+f_i)$是有$\frac{n?i}{n}$的概率按錯，如果按錯了，就先計算到i+1的1步，然后走回來要加$f_{i+1}$，再加上想要按到i-1的期望$f_i$
$$\begin{array}{rl}{f}_i& =\frac{i}{n}+\frac{n?i}{n}\times (1+f_{i+1}+f_i)\\ & \\ f_i& =\frac{i}{n}+\frac{n?i}{n}+\frac{n?i}{n}\times f_{i+1}+\frac{n?i}{n}\times f_i\\ & \\ f_i\times (1?\frac{n?i}{n})& =\frac{i}{n}+\frac{n?i}{n}+\frac{n?i}{n}\times f_{i+1}\\ & \\ \frac{i}{n}\times f_i& =\frac{i}{n}+\frac{n?i}{n}+\frac{n?i}{n}\times f_{i+1}\\ & \\ f_i& =\frac{i+n?i+(n?i)\times f_{i+1}}{i}\\ & \\ f_i& =\frac{n+(n?i)\times f_{i+1}}{i}\end{array}$$
那么就得到了關于f的遞推式
當遞推到k時，直接加k就行了

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define wyc 100003 #define N 100010 using namespace std; ll n, k, ans, sum, a[N], f[N], p[N]; ll Counting(ll x, ll y) {ll z = 1;while(y){if (y&1) z = z * x % wyc;x = x * x % wyc;y >>= 1;}return z; } int main() {scanf("%lld%lld", &n, &k);for (ll i = 1; i <= n; ++i)scanf("%lld", &a[i]);for (ll i = n; i > 0; --i){for (ll j = 2; i * j <= n; ++j)//它的倍數按了，它也要按a[i] ^= p[i * j];if (a[i])//要再按{p[i] = 1;sum++;}}if (sum <= k) ans = sum;//如果小于直接最優解else{f[n] = 1;if (n == sum) ans = (ans + 1) % wyc;for (ll i = n - 1; i > k; --i){f[i] = (n + (n - i) * f[i + 1] % wyc) * Counting(i, wyc - 2) % wyc;//遞推if (i <= sum) ans = (ans + f[i]) % wyc;//計算期望值}ans = (ans + k) % wyc;//小于等于k，直接最優解}for (ll i = 1; i <= n; ++i)ans = ans * i % wyc;//乘階乘printf("%lld", ans);return 0; }

總結

以上是生活随笔為你收集整理的【期望】关灯游戏（金牌导航 期望-8）的全部內容，希望文章能夠幫你解決所遇到的問題。

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