[JSOI2015]symmetry

链接：https://www.luogu.com.cn/problem/P6083 题目描述：这个题则么这么卡常。 我们可以先想到一个$O(n^3)$的$dp$，令$dp_{i,j,k}$表示以$(i,j)$为左上角边长为$k$的正方形的对称情况，可以$hash$转移。 考虑优化，发现对于每一个中心点，其边长是单调的，所以可以二分边长，二维$hash$判断对称情况。 ``` #include #include #include #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") %:pragma GCC optimize("-fgcse") %:pragma GCC optimize("-fgcse-lm") %:pragma GCC optimize("-fipa-sra") %:pragma GCC optimize("-ftree-pre") %:pragma GCC optimize("-ftree-vrp") %:pragma GCC optimize("-fpeephole2") %:pragma GCC optimize("-ffast-math") %:pragma GCC optimize("-fsched-spec") %:pragma GCC optimize("unroll-loops") %:pragma GCC optimize("-falign-jumps") %:pragma GCC optimize("-falign-loops") %:pragma GCC optimize("-falign-labels") %:pragma GCC optimize("-fdevirtualize") %:pragma GCC optimize("-fcaller-saves") %:pragma GCC optimize("-fcrossjumping") %:pragma GCC optimize("-fthread-jumps") %:pragma GCC optimize("-funroll-loops") %:pragma GCC optimize("-fwhole-program") %:pragma GCC optimize("-freorder-blocks") %:pragma GCC optimize("-fschedule-insns") %:pragma GCC optimize("inline-functions") %:pragma GCC optimize("-ftree-tail-merge") %:pragma GCC optimize("-fschedule-insns2") %:pragma GCC optimize("-fstrict-aliasing") %:pragma GCC optimize("-fstrict-overflow") %:pragma GCC optimize("-falign-functions") %:pragma GCC optimize("-fcse-skip-blocks") %:pragma GCC optimize("-fcse-follow-jumps") %:pragma GCC optimize("-fsched-interblock") %:pragma GCC optimize("-fpartial-inlining") %:pragma GCC optimize("no-stack-protector") %:pragma GCC optimize("-freorder-functions") %:pragma GCC optimize("-findirect-inlining") %:pragma GCC optimize("-fhoist-adjacent-loads") %:pragma GCC optimize("-frerun-cse-after-loop") %:pragma GCC optimize("inline-small-functions") %:pragma GCC optimize("-finline-small-functions") %:pragma GCC optimize("-ftree-switch-conversion") %:pragma GCC optimize("-foptimize-sibling-calls") %:pragma GCC optimize("-fexpensive-optimizations") %:pragma GCC optimize("-funsafe-loop-optimizations") %:pragma GCC optimize("inline-functions-called-once") %:pragma GCC optimize("-fdelete-null-pointer-checks") #define mod 998244353 #define line1 23 #define line2 131 using namespace std; char b[501][501]; int r,a[1022][1022],first,last,mid,n,ans[8][1022][1022],res[8]; long long map[8][1022][1022],fast_pow[1022],fast_pow2[1022]; inline long long f_sum(register int k,register int l,register int r,register int x) { if (l<r||k==0||k==2||k==4||k==6) return="" ((map[k][x][r]-map[k][x][l-1]*fast_pow[r-l+1]%mod)%mod+mod)%mod;="" else="" ((map[k][x][r]-map[k][x][l+1]*fast_pow[l-r+1]%mod)%mod+mod)%mod;="" }="" inline="" long="" f_sum(register="" int="" k,register="" l,register="" r,register="" l2,register="" r2)="" {="" if="" (l<r||k="=0||k==1||k==4||k==5)" ((f_sum(k,l2,r2,r)-f_sum(k,l2,r2,l-1)*fast_pow2[r-l+1]%mod)%mod+mod)%mod;="" ((f_sum(k,l2,r2,r)-f_sum(k,l2,r2,l+1)*fast_pow2[l-r+1]%mod)%mod+mod)%mod;="" main()="" scanf("%d",&n);="" for="" (register="" i="1;i<=n;++i)" j="1;j<=n;++j)" while="" (b[i][j]!="0" &&b[i][j]!="1" )="" b[i][j]="getchar();" a[i][j]="b[i][j]-'0';" fast_pow[0]="fast_pow2[0]=1;" (int="" fast_pow[i]="fast_pow[i-1]*line1%mod;" fast_pow2[i]="fast_pow2[i-1]*line2%mod;" map[0][i][j]="(map[0][i][j-1]*line1+a[i][j])%mod;">=1;--j) map[1][i][j]=(map[1][i][j+1]*line1+a[i][j])%mod; for (register int i=1;i<=n;++i) for (register int j=n;j>=1;--j) map[1][i][j]=(map[1][i-1][j]*line2+map[1][i][j])%mod; for (register int i=n;i>=1;--i) for (register int j=1;j<=n;++j) map[2][i][j]=(map[2][i][j-1]*line1+a[i][j])%mod; for (register int i=n;i>=1;--i) for (register int j=1;j<=n;++j) map[2][i][j]=(map[2][i+1][j]*line2+map[2][i][j])%mod; for (register int i=n;i>=1;--i) for (register int j=n;j>=1;--j) map[3][i][j]=(map[3][i][j+1]*line1+a[i][j])%mod; for (register int i=n;i>=1;--i) for (register int j=n;j>=1;--j) map[3][i][j]=(map[3][i+1][j]*line2+map[3][i][j])%mod; for (register int i=1;i<=n;++i) for (register int j=1;j<=n;++j) map[4][i][j]=(map[4][i][j-1]*line1+a[j][i])%mod; for (register int i=1;i<=n;++i) for (register int j=1;j<=n;++j) map[4][i][j]=(map[4][i-1][j]*line2+map[4][i][j])%mod; for (register int i=1;i<=n;++i) for (register int j=n;j>=1;--j) map[5][i][j]=(map[5][i][j+1]*line1+a[j][i])%mod; for (register int i=1;i<=n;++i) for (register int j=n;j>=1;--j) map[5][i][j]=(map[5][i-1][j]*line2+map[5][i][j])%mod; for (register int i=n;i>=1;--i) for (register int j=1;j<=n;++j) map[6][i][j]=(map[6][i][j-1]*line1+a[j][i])%mod; for (register int i=n;i>=1;--i) for (register int j=1;j<=n;++j) map[6][i][j]=(map[6][i+1][j]*line2+map[6][i][j])%mod; for (register int i=n;i>=1;--i) for (register int j=n;j>=1;--j) map[7][i][j]=(map[7][i][j+1]*line1+a[j][i])%mod; for (register int i=n;i>=1;--i) for (register int j=n;j>=1;--j) map[7][i][j]=(map[7][i+1][j]*line2+map[7][i][j])%mod; for (register double i=1;i<=n;i+=0.5) for (register double j=1+0.5*(floor(i)!=i);j<=n;++j) { first=0; last=min(n+1-max(i,j),min(i,j))-1; while (first<=last) { mid=(first+last)/2; if (F_sum(0,floor(i-mid),ceil(i+mid),floor(j-mid),ceil(j+mid))==F_sum(1,floor(i-mid),ceil(i+mid),ceil(j+mid),floor(j-mid))) { first=mid+1; ans[1][(int)(i)][(int)(j)]=max(ans[1][(int)(i)][(int)(j)],mid*2+(floor(i)!=i)); } else last=mid-1; } first=0; last=min(n+1-max(i,j),min(i,j))-1; while (first<=last) { mid=(first+last)/2; if (F_sum(0,floor(i-mid),ceil(i+mid),floor(j-mid),ceil(j+mid))==F_sum(2,ceil(i+mid),floor(i-mid),floor(j-mid),ceil(j+mid))) { first=mid+1; ans[2][(int)(i)][(int)(j)]=max(ans[2][(int)(i)][(int)(j)],mid*2+(floor(i)!=i)); } else last=mid-1; } first=0; last=min(n+1-max(i,j),min(i,j))-1; while (first<=last) { mid=(first+last)/2; if (F_sum(0,floor(i-mid),ceil(i+mid),floor(j-mid),ceil(j+mid))==F_sum(3,ceil(i+mid),floor(i-mid),ceil(j+mid),floor(j-mid))) { first=mid+1; ans[3][(int)(i)][(int)(j)]=max(ans[3][(int)(i)][(int)(j)],mid*2+(floor(i)!=i)); } else last=mid-1; } first=0; last=min(n+1-max(i,j),min(i,j))-1; while (first<=last) { mid=(first+last)/2; if (F_sum(0,floor(i-mid),ceil(i+mid),floor(j-mid),ceil(j+mid))==F_sum(4,floor(j-mid),ceil(j+mid),floor(i-mid),ceil(i+mid))) { first=mid+1; ans[4][(int)(i)][(int)(j)]=max(ans[4][(int)(i)][(int)(j)],mid*2+(floor(i)!=i)); } else last=mid-1; } first=0; last=min(n+1-max(i,j),min(i,j))-1; while (first<=last) { mid=(first+last)/2; if (F_sum(0,floor(i-mid),ceil(i+mid),floor(j-mid),ceil(j+mid))==F_sum(5,floor(j-mid),ceil(j+mid),ceil(i+mid),floor(i-mid))) { first=mid+1; ans[5][(int)(i)][(int)(j)]=max(ans[5][(int)(i)][(int)(j)],mid*2+(floor(i)!=i)); } else last=mid-1; } first=0; last=min(n+1-max(i,j),min(i,j))-1; while (first<=last) { mid=(first+last)/2; if (F_sum(0,floor(i-mid),ceil(i+mid),floor(j-mid),ceil(j+mid))==F_sum(6,ceil(j+mid),floor(j-mid),floor(i-mid),ceil(i+mid))) { first=mid+1; ans[6][(int)(i)][(int)(j)]=max(ans[6][(int)(i)][(int)(j)],mid*2+(floor(i)!=i)); } else last=mid-1; } first=0; last=min(n+1-max(i,j),min(i,j))-1; while (first<=last) { mid=(first+last)/2; if (F_sum(0,floor(i-mid),ceil(i+mid),floor(j-mid),ceil(j+mid))==F_sum(7,ceil(j+mid),floor(j-mid),ceil(i+mid),floor(i-mid))) { first=mid+1; ans[7][(int)(i)][(int)(j)]=max(ans[7][(int)(i)][(int)(j)],mid*2+(floor(i)!=i)); } else last=mid-1; } } for (register int i=1;i<=n;++i) for (register int j=1;j<=n;++j) { res[0]=max(res[0],min(min(min(ans[1][i][j],ans[2][i][j]),ans[4][i][j]),ans[7][i][j])); res[1]=max(res[1],min(min(ans[5][i][j],ans[6][i][j]),ans[3][i][j])); res[2]=max(res[2],min(ans[1][i][j],ans[2][i][j])); res[2]=max(res[2],min(ans[4][i][j],ans[7][i][j])); res[3]=max(res[3],ans[3][i][j]); res[4]=max(res[4],ans[1][i][j]); res[4]=max(res[4],ans[2][i][j]); res[4]=max(res[4],ans[4][i][j]); res[4]=max(res[4],ans[7][i][j]); } printf("%d %d %d %d %d\n",res[0]+1,res[1]+1,res[2]+1,res[3]+1,res[4]+1); return 0; }