傳送門

文章目錄

• 解析
• 代碼

解析

首先，開關開關兩次等于沒動，所有對于一個解來說，開關的狀態只有開與不開之分
接下來的一個關鍵點是：每一個開關的效果無法被其他開關操作的組合代替
所以這個題應該只有唯一解

那么我們可以不計代價，只要考慮怎么搞出這個解就行了
因為一個開關只能影響因數，所以從大到小考慮遇見亮的燈無腦關就一定可以完成任務
既然唯一解，那么這個解就是它了

那么我們找出了這個解需要的操作數，記為cnt
那么顯然的是，cnt<=k時，期望就是cnt

接下來考慮cnt>k的情況
設計dp：

f[i]表示**從剩i個燈要操作轉移到(i-1)個燈要操作的期望步數

考慮下一步，有i/n的概率選到對的燈，(n-i)/n的概率選錯，需要回到(i+1)的狀態
那么可以得到
$$f_i=i/n?1+(n?i)/n?(f[i+1]+f_i+1)$$
移項整理一下，得到：
$$f_i=(n+(n?i)?f[i+1])/i$$

統計答案從f_k+1加到f_cnt即可
最后再+k

不要忘了階乘!

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e5+100; const int mod=100003; ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m,k,cnt; int op[N]; ll f[N]; void work(int x){int top=floor(sqrt(x));for(int i=1;i<=top;i++){if(x%i==0){op[i]^=1;if(x/i!=i) op[x/i]^=1;}} } void Mod(double &x){x-=mod*(floor(x/mod)); } ll ksm(ll x,int k){ll res=1;while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res; } int main(){n=read();k=read();for(int i=1;i<=n;i++) op[i]=read();for(int i=n;i>=1;i--){if(op[i]){work(i);cnt++;}}f[n]=1;for(int i=n-1;i>k;i--){f[i]=(n+1ll*(n-i)*f[i+1]%mod)*ksm(i,mod-2)%mod;//Mod(f[i]);}ll res=0;if(cnt<=k) res=cnt;else{for(int i=cnt;i>k;i--){res=(res+f[i])%mod; }res+=k;}for(int i=1;i<=n;i++){res=res*i%mod;//assert(jc>=0);}printf("%lld",res); } /* 3 1 3 4 5 1 4 7 3 9 3 2 2 */

總結

以上是生活随笔為你收集整理的YBTOJ洛谷P3750：分手是祝愿（期望dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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