【NTT】【二维卷积】最佳农场
发布时间
阅读量：
阅读量
题意：
分析：
经过翻转矩阵处理后可被视为二维卷积操作。
将位置坐标(i,j)对应到多项式中的某一项之后进行一维卷积运算。
听起来很有雄心壮志却略显自相矛盾。
多的位置用0补齐即可。
复杂度O(R*C+R*C*log(R*C))
#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 1000010
#define MAXM 510
#define MOD 998244353
using namespace std;
typedef long long ll;
ll fsp(ll x,int y){
ll res=1;
while(y){
if(y&1)
res=res*x%MOD;
x=x*x%MOD;
y>>=1;
}
return res;
}
const int GG=3;
void NTT(ll A[],int N,int flag){
for(int i=1,j=0;i<N;i++){
for(int d=N;j^=d>>=1,~j&d;);
if(i<j)
swap(A[i],A[j]);
}
for(int i=1;i<N;i<<=1){
ll wn=fsp(GG,(MOD-1)/(i<<1));
if(flag)
wn=fsp(wn,MOD-2);
for(int j=0;j<N;j+=(i<<1)){
ll w=1;
for(int k=0;k<i;k++,w=w*wn%MOD){
ll X=A[j+k],Y=w*A[i+j+k]%MOD;
A[j+k]=(X+Y)%MOD;
A[i+j+k]=(X-Y+MOD)%MOD;
}
}
}
if(flag)
for(ll i=0,invN=fsp(N,MOD-2);i<N;i++)
A[i]=A[i]*invN%MOD;
}
char s[MAXM][MAXM];
int n,m;
ll g[MAXN],l[MAXN],g1[MAXN],l1[MAXN],f[MAXN],p,tot;
void prepare(ll G[],ll L[]){
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
G[i*m+j]=(s[i][j]=='G');
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
L[i*m+j]=(s[i][j]=='L');
NTT(G,p,0);
NTT(L,p,0);
}
void calc(){
memset(f,0,sizeof f);
for(int i=0;i<p;i++)
f[i]=(g[i]*g1[i]%MOD+l[i]*l1[i]%MOD)%MOD;
NTT(f,p,1);
}
int main(){
freopen("best.in","r",stdin);
freopen("best.out","w",stdout);
int n1,m1;
SF("%d%d",&n,&m);
p=1,tot=n*m;
while(p<=tot*2)
p<<=1;
for(int i=0;i<n;i++)
SF("%s",s[i]);
prepare(g,l);
int B;
SF("%d",&B);
while(B--){
memset(s,0,sizeof s);
memset(g1,0,sizeof g1);
memset(l1,0,sizeof l1);
SF("%d%d",&n1,&m1);
for(int i=0;i<n1;i++)
SF("%s",s[i]);
for(int i=0;i<n1;i++)
reverse(s[i],s[i]+m1);
for(int i=0;i<n1&&i<n1-i-1;i++)
swap(s[i],s[n1-i-1]);
prepare(g1,l1);
calc();
ll ans=0;
int ansx=-1,ansy=-1;
for(int i=n1-1;i<n;i++)
for(int j=m1-1;j<m;j++)
if(ansx==-1||ans<f[i*m+j]){
ansx=i-n1+1;
ansy=j-m1+1;
ans=f[i*m+j];
}
PF("%d %d\n",ansx+1,ansy+1);
}
}
代码解释全部评论 (0)
还没有任何评论哟~