为什么按照题解赋值 σ 可以通过,而以下这种方式则不行:
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("inline")
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
#include<bits/stdc++.h>
#define ll __int128
#define int long long
#define ld long double
using namespace std;
const ll N=3e5+20,M=1e6+20,mod=20190816170251ll;
inline int read(){
int d=0,f=1;char x=getchar();
while(x<'0'||x>'9'){if(x=='-'){f=-1;}x=getchar();}
while(x>='0'&&x<='9'){d=(d<<1)+(d<<3)+(x-48);x=getchar();}
return d*f;
}
void exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return;}exgcd(b,a%b,x,y);ll tmp=x;x=y;y=tmp-(a/b)*y;}
ll inv(ll a,ll b){ll x,y;exgcd(a,b,x,y);x%=b;x+=b;x%=b;return x;}
int a[N],sg[N],p,q,id,n;
ld o[4]={0,0.8047378541243,0.5464101615137,0.61803398874989};
inline int O(int x){
if(id>3) return floor(1.*x*p/q);
else return floor(1.*x*o[id]);
}
inline int SG(int x){
int t1=O(x);int t2=O(x-t1);
if(!t1) return 0;
if(t1>t2) return t1;
else return t1==1?t1:t1-1;
}
signed main(){
id=read();n=read();
for(int i=1;i<=n;i++) a[i]=sg[i]=read();
o[1]=(1.L*sqrtl(2.L)+1)/3,o[2]=(1.L*sqrtl(3.L)+1)/5,o[3]=(1.L*sqrtl(5.L)-1)/2;
// cout<<o[3];
if(id>3) p=read(),q=read();
int s=0,ans=0,d=0;
for(int i=1;i<=n;i++) sg[i]=SG(a[i]),s=s^sg[i],d+=O(a[i])!=0;
// for(int i=1;i<=n;i++) printf("%lld %lld\n",O(1),sg[i]);
for(int i=1;i<=n;i++){
if(!O(a[i])) continue;
int t=s;t^=sg[i];
if(O(a[i])!=sg[i]){
if(SG(a[i]-O(a[i]))==t) ans=(ans+inv(O(a[i]),mod))%mod;
}
if(t<sg[i]) ans=(ans+inv(O(a[i]),mod))%mod;
}
printf("%lld\n",(int)(inv(d,mod)*ans%mod));
return 0;
}
其部分代码为:
o[1]=(1.L*sqrtl(2.L)+1)/3,o[2]=(1.L*sqrtl(3.L)+1)/5,o[3]=(1.L*sqrtl(5.L)-1)/2;