问题在于对 1000000000 (109)这个数字的调用方式,当直接使用这个数字时,对于 P3546 这道题可以通过,但是当使用一个 int 类型的变量赋值为 1000000000 (109),并调用它时,对于此题就无法通过。
其一:由于本代码使用的是 随机数Hash 的解法,为了避免由于 rp 问题导致 WA ,特意对以上两种情况都交了 5 次,发现该 WA 还是 WA ,该 AC 还是 AC 。
其二:为了验证是由于1000000000 (109)这个数字的调用不同导致了不同的结果,又再直接调用 1000000000 (109)这个数字时,强制转换成了 int 类型,然后就 WA 了。由于第一条里的原因,再次提交了 5 次,发现结果也并没有任何改变,所以排除了是 rp 问题导致的 WA 。
综上可以证明:一定是 对于 1000000000 (109)这个数字的调用不同导致了不同的结果。所以直接调用和存在一个 int 类型 变量里调用有何区别?
WA代码 (赋值给一个 int 类型变量):
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fd(i,a,b) for(int i=a,_i=b;i<=_i;i=-~i)
#define bd(i,a,b) for(int i=a,_i=b;i>=_i;i=~-i)
using namespace std;
const int N=2e6+509,MT=2;
int MAX_NUM=1000000000;
int n,m,f[N],ans,_L;
char s[N];
inline int read(){int x;scanf("%lld",&x);return x;}
inline void write(int x,int F=1)
{
if(F==0) printf("%lld",x);
else if(F==1) printf("%lld\n",x);
else printf("%lld ",x);
}
struct My_Hash
{
int mod=998244353,seed=131;
int p[N],Pw[N];
inline int Hash(int l,int r) {return ((p[r]-p[l-1]*Pw[r-l+1]%mod+mod)%mod);}
inline void Pre()
{
Pw[0]=1;
fd(i,1,n)
{
p[i]=(p[i-1]*seed+s[i])%mod;
Pw[i]=Pw[i-1]*seed%mod;
}
}
inline void Named(int _mod_,int _seed_) {mod=_mod_,seed=_seed_;}
inline void Set(int Mod) {Named(rand()%Mod*Mod+rand()%Mod,131);}
}H[MT+1];
inline bool Check_Diff(int l,int r,int L,int R)
{
/*
int Need = (MT>3)?MT-2:MT-1,num=0;
fd(i,0,MT)
if(H[i].Hash(l,r)!=H[i].Hash(L,R))
num++;
if(num>Need) return 1;
return 0;
*/
fd(i,0,MT)
if(H[i].Hash(l,r)==H[i].Hash(L,R))
return 0;
return 1;
}
inline bool Check_Same(int l,int r,int L,int R)
{
fd(i,0,MT)
if(H[i].Hash(l,r)!=H[i].Hash(L,R))
return 0;
return 1;
}
signed main()
{
#define FJ
#ifndef FJ
freopen("bzoj1066_.in","r",stdin);
freopen("bzoj1066_.out","w",stdout);
#endif
n=read();m=n/2;
scanf("%s",s+1);
H[0].Named(2654435769,131);//存疑
H[1].Named(1610612741,131);//Good
//998244353 1e9+7//貌似容易被×
// 貌似可以:
srand(time(0));
fd(i,2,MT) H[i].Set(MAX_NUM);
// ?
fd(i,0,MT) H[i].Pre();
bd(i,m,0)
{
_L=min(_L+2,m-i);
while(_L>0&&Check_Diff(i+1,i+_L,n-i-_L+1,n-i)) _L--;
if(Check_Same(1,i,n-i+1,n)) ans=max(ans,i+_L);
}
write(ans);
return 0;
}
WA代码 (调用时将 1000000000 (109)强制转换成 int ):
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fd(i,a,b) for(int i=a,_i=b;i<=_i;i=-~i)
#define bd(i,a,b) for(int i=a,_i=b;i>=_i;i=~-i)
using namespace std;
const int N=2e6+509,MT=2;
int MAX_NUM=1000000000;
int n,m,f[N],ans,_L;
char s[N];
inline int read(){int x;scanf("%lld",&x);return x;}
inline void write(int x,int F=1)
{
if(F==0) printf("%lld",x);
else if(F==1) printf("%lld\n",x);
else printf("%lld ",x);
}
struct My_Hash
{
int mod=998244353,seed=131;
int p[N],Pw[N];
inline int Hash(int l,int r) {return ((p[r]-p[l-1]*Pw[r-l+1]%mod+mod)%mod);}
inline void Pre()
{
Pw[0]=1;
fd(i,1,n)
{
p[i]=(p[i-1]*seed+s[i])%mod;
Pw[i]=Pw[i-1]*seed%mod;
}
}
inline void Named(int _mod_,int _seed_) {mod=_mod_,seed=_seed_;}
inline void Set(int Mod) {Named(rand()%((int)1000000000)*((int)1000000000)+rand()%((int)1000000000),131);}
}H[MT+1];
inline bool Check_Diff(int l,int r,int L,int R)
{
/*
int Need = (MT>3)?MT-2:MT-1,num=0;
fd(i,0,MT)
if(H[i].Hash(l,r)!=H[i].Hash(L,R))
num++;
if(num>Need) return 1;
return 0;
*/
fd(i,0,MT)
if(H[i].Hash(l,r)==H[i].Hash(L,R))
return 0;
return 1;
}
inline bool Check_Same(int l,int r,int L,int R)
{
fd(i,0,MT)
if(H[i].Hash(l,r)!=H[i].Hash(L,R))
return 0;
return 1;
}
signed main()
{
#define FJ
#ifndef FJ
freopen("bzoj1066_.in","r",stdin);
freopen("bzoj1066_.out","w",stdout);
#endif
n=read();m=n/2;
scanf("%s",s+1);
H[0].Named(2654435769,131);//存疑
H[1].Named(1610612741,131);//Good
//998244353 1e9+7//貌似容易被×
// 貌似可以:
srand(time(0));
fd(i,2,MT) H[i].Set(MAX_NUM);
// ?
fd(i,0,MT) H[i].Pre();
bd(i,m,0)
{
_L=min(_L+2,m-i);
while(_L>0&&Check_Diff(i+1,i+_L,n-i-_L+1,n-i)) _L--;
if(Check_Same(1,i,n-i+1,n)) ans=max(ans,i+_L);
}
write(ans);
return 0;
}
AC代码(直接用 )
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fd(i,a,b) for(int i=a,_i=b;i<=_i;i=-~i)
#define bd(i,a,b) for(int i=a,_i=b;i>=_i;i=~-i)
using namespace std;
const int N=2e6+509,MT=2;
int MAX_NUM=1000000000;
int n,m,f[N],ans,_L;
char s[N];
inline int read(){int x;scanf("%lld",&x);return x;}
inline void write(int x,int F=1)
{
if(F==0) printf("%lld",x);
else if(F==1) printf("%lld\n",x);
else printf("%lld ",x);
}
struct My_Hash
{
int mod=998244353,seed=131;
int p[N],Pw[N];
inline int Hash(int l,int r) {return ((p[r]-p[l-1]*Pw[r-l+1]%mod+mod)%mod);}
inline void Pre()
{
Pw[0]=1;
fd(i,1,n)
{
p[i]=(p[i-1]*seed+s[i])%mod;
Pw[i]=Pw[i-1]*seed%mod;
}
}
inline void Named(int _mod_,int _seed_) {mod=_mod_,seed=_seed_;}
inline void Set(int Mod) {Named(rand()%1000000000*1000000000+rand()%1000000000,131);}
}H[MT+1];
inline bool Check_Diff(int l,int r,int L,int R)
{
/*
int Need = (MT>3)?MT-2:MT-1,num=0;
fd(i,0,MT)
if(H[i].Hash(l,r)!=H[i].Hash(L,R))
num++;
if(num>Need) return 1;
return 0;
*/
fd(i,0,MT)
if(H[i].Hash(l,r)==H[i].Hash(L,R))
return 0;
return 1;
}
inline bool Check_Same(int l,int r,int L,int R)
{
fd(i,0,MT)
if(H[i].Hash(l,r)!=H[i].Hash(L,R))
return 0;
return 1;
}
signed main()
{
#define FJ
#ifndef FJ
freopen("bzoj1066_.in","r",stdin);
freopen("bzoj1066_.out","w",stdout);
#endif
n=read();m=n/2;
scanf("%s",s+1);
H[0].Named(2654435769,131);//存疑
H[1].Named(1610612741,131);//Good
//998244353 1e9+7//貌似容易被×
// 貌似可以:
srand(time(0));
fd(i,2,MT) H[i].Set(MAX_NUM);
// ?
fd(i,0,MT) H[i].Pre();
bd(i,m,0)
{
_L=min(_L+2,m-i);
while(_L>0&&Check_Diff(i+1,i+_L,n-i-_L+1,n-i)) _L--;
if(Check_Same(1,i,n-i+1,n)) ans=max(ans,i+_L);
}
write(ans);
return 0;
}