题目描述
传送门: https://www.acwing.com/problem/content/2801/
样例
4 0
0 0 1 1
解法
好吧其实我是被题目骗过来的。。。
貌似题目和内容一点关系都没有。(雾)
思路:乍一看和高斯消元的某道题好像,仔细一看似乎没什么关系。。。
先找出来一个理想状态可以开最少灯达到条件。
肯定是从最大往最小调。(这不显然嘛)
因为大的会影响小的,把小的都调好了一改大的就全乱了(但是也有可能比较碰巧后面又把前面弄好了)
就比如1 0 1从前往后和从后往前都一样,不过大多数都是从后往前就像1 1 0 1从后往前调只需要一步(调第四个就行)
知道理想方案后动那几个灯的先后顺序就无所谓了,先调哪个都一样。
f[i]数组用来记录理想方案从i到i-1的期望步数,i是还差几个灯亮着。
显然当i<=k的时候f[i]=1;
如果i>k易得f[i]=n/i+(n-i)*f[i+1]/i.
因为f[i]=i/n+(n-i)/n(f[i]+f[i+1]+1),化简可得
i/n的几率动那么理想方案需要动的灯,(n-i)的几率动非理想方案的灯,就要动f[i+1]调回i状态然后f[i]调到i-1,动错的这一步也要算所以要+1。
最后用个ans把f[1~n]全部加起来就行。
要从后往前推,因为是概率Dp嘛。然后把f[n]初始化为1,因为一共n个,调到n-1这肯定是1嘛。。。
最后要用乘法逆元因为用double除法算好像%的时候会出错,好像%只能用于int或者long long之类的。。。(我太蒻了不知道。。。)
细节看代码吧
Code
#include<bits/stdc++.h>
using namespace std;
const long long p=100003;
long long s=1,f[100005],ans=0,inv[100005];
int a[100005];
void dp(int x)//动一个开关会对其约数有影响
{
int d=sqrt(x);
for(int i=1;i<=d;i++)
{
if(x%i==0)
{
a[i]^=1;
if(i*i!=x)
a[x/i]^=1;
}
}
}
int main()
{
int n,k,t=0;
scanf("%d%d",&n,&k);
inv[0]=1,inv[1]=1;
for(int i=2;i<=n;i++)//线性求逆元
inv[i]=(p-p/i)*inv[p%i]%p;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=n;i>=1;i--)//找最理想方案
if(a[i]==1)
{
t++;//t记录理想方案的布数,只要有一个灯亮着就要调。
dp(i);
}
f[n]=1;
for(int i=1;i<=k;i++)//处理需要布数小于K的,我忘了处理浪费了10几分钟。。。
f[i]=1;
for(int i=n-1;i>k;i--)//从n-1开始求但是需要的到t就行,多的那部分我理解的是从全部打开的状态调为理想方案的状态的期望,也就是题目给的初始状态或者和初始状态等价的某种状态。
f[i]=(n+(n-i)*f[i+1]%p)%p*inv[i]%p;
for(int i=1;i<=t;i++)
ans+=f[i]%p;
for(int i=1;i<=n;i++)//别忘了乘n的阶乘
s=s*i%p;
ans=s*ans%p;//要%p
printf("%lld\n",ans);
}