NC20437. [SHOI2017]分手是祝愿
描述
输入描述
第一行两个整数 n, k。
接下来一行 n 个整数，每个整数是 0 或者 1，其中第 i 个整数表示第 i 个灯的初始情况。
1 ≤ n ≤ 100000, 0 ≤ k ≤ n；
输出描述
输出一行，为操作次数的期望乘以 n 的阶乘对 100003 取模之后的结果。
示例1
输入:
4 0 0 0 1 1
输出:
512
C++ 解法, 执行用时: 11ms, 内存消耗: 1292K, 提交时间: 2021-05-21 22:05:00
#include<cstdio>
#define maxn 100005
#define mod 100003
using namespace std;
int g[maxn],v[maxn],a[maxn],inv[maxn];
int main(){
int n,m,i,j,k,fac;
//freopen("input.in","r",stdin);
scanf("%d%d",&n,&m);
for(i=fac=1;i<=n;fac=1ll*fac*i%mod,i++)scanf("%d",&a[i]);
for(i=n,k=0;i;i--){
for(j=2*i;j<=n;j+=i)a[i]^=v[j];
k+=(v[i]=a[i]);
}
if(k<=m)printf("%d",1ll*fac*k%mod);
else{
for(inv[1]=1,i=2;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(g[n]=i=1;i<=m;i++)g[i]=1;
for(i=n-1;i>m;i--)g[i]=(1ll*(n-i)*g[i+1]%mod+n)*inv[i]%mod;
for(i=1,j=0;i<=k;i++)j=(j+1ll*g[i]*fac%mod)%mod;
printf("%d",j);
}
return 0;
}