解题思路

这道题目要求我们在一个$n$维矩阵$S$中找到一个位置$(p_1, p_2, \dots, p_n)$，使得$T$矩阵的所有元素与$S$中从$(p_1, p_2, \dots, p_n)$开始的对应位置元素完全匹配。由于$n$可能高达10，直接暴力检查所有可能的起始位置显然不可行，因此需要一种高效的匹配方法。

关键思路

1. 滚动哈希（Rolling Hash）：我们使用滚动哈希技术来高效计算和比较$S$和$T$的子矩阵的哈希值。具体来说，我们为$T$计算一个目标哈希值，然后在$S$中寻找所有可能的子矩阵，计算其哈希值并与目标哈希值比较。

2. 多维哈希计算：对于$n$维矩阵，我们需要逐维计算哈希值。具体步骤如下：

   • 首先为$T$计算一个目标哈希值target。
   • 然后为$S$中所有可能的子矩阵（与$T$大小相同）计算哈希值，并与target比较。

3. 字典序最小的匹配位置：由于题目要求输出字典序最小的匹配位置，我们按照从小到大的顺序遍历$S$的所有可能起始位置，一旦找到匹配的位置即可立即输出。

#include<cstdio>
#define N 500010
int n,i,j,t,delta,ca,cb,a[10],b[10],c[N],d[N],p[N][10];
int seed[10]={233,13331,997,733,811,953,2011,1999,1997,1801};
unsigned int pow,target,f[11][N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
int main(){
  read(n);
  for(i=0,ca=1;i<n;i++)read(a[i]),ca*=a[i];
  for(i=0,cb=1;i<n;i++)read(b[i]),cb*=b[i];
  for(i=0;i<ca;i++)read(c[i]);
  for(i=0;i<cb;i++)read(d[i]);
  for(i=0;i<cb;i++)for(t=i,j=n-1;~j;j--)p[i][j]=t%b[j],t/=b[j];
  for(j=0;j<cb;j++)f[n][j]=d[j];
  for(delta=1,i=n-1;~i;i--){
    for(j=0;j<cb;j++){
      f[i][j]=f[i+1][j];
      if(p[j][i])f[i][j]+=f[i][j-delta]*seed[i];
    }
    delta*=b[i];
  }
  target=f[0][cb-1];
  for(i=0;i<ca;i++)for(t=i,j=n-1;~j;j--)p[i][j]=t%a[j],t/=a[j];
  for(j=0;j<ca;j++)f[n][j]=c[j];
  for(delta=1,i=n-1;~i;i--){
    for(pow=1,j=b[i];j;j--)pow*=seed[i];
    for(j=0;j<ca;j++){
      f[i][j]=f[i+1][j];
      if(p[j][i])f[i][j]+=f[i][j-delta]*seed[i];
      if(p[j][i]>=b[i])f[i][j]-=f[i+1][j-delta*b[i]]*pow;
    }
    delta*=a[i];
  }
  for(j=0;j<ca;j++){
    for(t=1,i=0;i<n;i++)if(p[j][i]<b[i]-1){t=0;break;}
    if(t&&f[0][j]==target){
      for(i=0;i<n;i++)printf("%d ",p[j][i]-b[i]+2);
      return 0;
    }
  }
}