疑惑
查看原帖
疑惑
436389
Vidoliga楼主2023/9/11 20:04

为什么按照题解赋值 σ\sigma 可以通过,而以下这种方式则不行:

#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;
2023/9/11 20:04
加载中...