期望简单题。
首先简单观察，最优策略是每次选择一个编号最大的亮的灯进行操作，直到所有灯熄灭。通过此策略，容易发现如果，一个灭的灯被操作到，那么一定会再次对这个灯进行操作。
于是先处理出最优策略下操作的灯的个数 $p$，暴力枚举即可做到 $\mathcal O(n\ln n)$，但显然可以直接使用 Dirichlet 后缀和逆向操作做到 $\mathcal O(n\log \log n)$。
接着考虑 DP，设计状态 $f(i)$ 表示从至少操作 $i$ 次到至少操作 $i-1$ 期望操作多少次。考虑意义，要么选中必须操作的；要么选中不用操作，我们需要从 $f(i+1)$ 操作回来再继续操作。列出式子并整理：
递推即可，最终答案为 $\sum_{i>k} f(i)$。时间复杂度为 $\mathcal O(n\log \log n)$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10,mod=1e5+3;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,k,res;
int a[N];
bool vis[N];
int tot,prime[N];
int inv[N],f[N];
inline void adj(int &x){x+=x>>31&mod;}
void sieve(int n)
{
inv[1]=1;
for(int i=2;i<=n;i++)
{
inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;
if(!vis[i])prime[++tot]=i;
for(int j=1;j<=tot&&1ll*i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(!(i%prime[j]))break;
}
}
}
int main()
{
read(n,k);
for(int i=1;i<=n;i++)read(a[i]);
sieve(n);
for(int i=tot;i;i--)
for(int j=1;j<=n/prime[i];j++)
a[j]^=a[j*prime[i]];
int fac=1;
for(int i=1;i<=n;i++)fac=1ll*fac*i%mod,res+=a[i];
if(res<=k)return printf("%d\n",1ll*res*fac%mod),0;
for(int i=n;i>k;i--)f[i]=(n+1ll*(n-i)*f[i+1])*inv[i]%mod;
int ans=k;
for(int i=res;i>k;i--)adj(ans+=f[i]-mod);
printf("%d\n",1ll*ans*fac%mod);
return 0;
}
|