一早上膝盖跪烂了ORZ出门右转膜题解谢谢
#include#include #include #include #include #include using namespace std;typedef long long LL;const int mod=100003;LL fac[110000],inv[110000];int a[110000];LL f[110000];int main(){ fac[1]=1,inv[1]=1; for(int i=2;i<=105000;i++)fac[i]=fac[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod; int n,k,num=0; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=n;i>=1;i--) if(a[i]==1) { for(int j=1;j*j<=i;j++) if(i%j==0) { a[j]^=1; if(j*j!=i)a[i/j]^=1; } num++; } if(num<=k){printf("%d\n",num*fac[n]%mod);return 0;} LL ans=0;f[n]=1; for(int i=n-1;i>k;i--)f[i]=(n+(n-i)*f[i+1])%mod*inv[i]%mod; for(int i=num;i>k;i--)ans=(ans+f[i])%mod; ans=(ans+k)%mod; printf("%d\n",ans*fac[n]%mod); return 0;}