前两天做过一个题意类似但做法不类似的题 在这里
首先做这道题需要一个结论：(一元)同余方程组有解的充要条件是方程组中的所有方程两两联立有解。证明 两个同余方程联立有解就用裴蜀定理判一下就行了。不用这个结论的话需要用CRT和一些数据结构解决，但是非常麻烦。
依次枚举每种数字i，尝试算出最长的全是i的子串。把n个序列中含有i的找出来，它们在所有n个中构成了一些连续段。这些连续段的长度之和是\(O(nk)\)的。对于每个连续段，求出这个段内部最长的全是i的子串。考虑从左到右枚举一个连续段中的每个位置r，算出以r为子串的右端点，左端点最左可以到哪里。令这个连续段中第j个位置对应的序列长度为\(N_j\)，这个序列中i所在的位置为\(A_j\)(下标从0开始)，则连续段中的每个位置都对应一个同余方程\(x \equiv A_j (mod \ N_j)\)。其实我们就是要找出最小的l，满足[l,r]中的同余方程联立成方程组是有解的。发现随着r的增加，l不会减少，所以可以用two-pointers。我们要做的是在当r增加1时，快速找出现在[l,r]中与位置r的方程联立无解的所有方程，并将其删除，同时增加l。发现如果两个方程N相同但A不同，联立一定无解，所以每时每刻，[l,r]中每个N只会有1种对应的A。所以每次r增加1，我们就枚举所有N(一共40种)，如果某个N对应的A表示的方程 与 r所对应的方程 联立无解，那么就把所有\(N_j\)等于这个N的方程删除。每种N对应的所有方程可以用vector维护。由于每个方程的N和A的值域都是40，所以可以预处理任意两种方程是否联立无解。
总复杂度\(O(nk^2+k^4logk)\)。(\(k^4logk\)是预处理复杂度)
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(0);
}
using namespace std;
int n,m,ans[100010],sz[100010];
bool bad[42][42][42][42];//a1,n1,a2,n2
vector <pii> poss[100010];
vector <int> pss[50];
void solve(int ii)
{
rep(i,45) pss[i].clear();
rep(i,poss[ii].size())
{
int p=i;while(p+1<poss[ii].size()&&poss[ii][p+1].fi==poss[ii][p].fi+1) ++p;
int cur=i;
set <int> st;
for(int ed=i;ed<=p;++ed)
{
st.insert(ed);
int mxdel=-1,kk=sz[poss[ii][ed].fi],aa=poss[ii][ed].se;
repn(j,40) if(pss[j].size())
{
int kkk=j,aaa=poss[ii][pss[j][0]].se;
if(bad[aa][kk][aaa][kkk])
{
mxdel=max(mxdel,pss[j].back());
pss[j].clear();
}
}
pss[kk].pb(ed);
while(*st.begin()<=mxdel) st.erase(st.begin());
ans[ii]=max(ans[ii],(int)st.size());
}
i=p;
}
}
int main()
{
fileio();
freopen("hypochondriac.in","r",stdin);
freopen("hypochondriac.out","w",stdout);
rep(i,40) for(int j=i+1;j<=40;++j) rep(ii,40) for(int jj=ii+1;jj<=40;++jj)
{
LL dv=__gcd(j,jj);
if(abs(i-ii)%dv!=0) bad[i][j][ii][jj]=true;
}
cin>>n>>m;
rep(i,n)
{
int x,y;
scanf("%d",&x);sz[i]=x;
rep(j,x)
{
scanf("%d",&y);
poss[y].pb(mpr(i,j));
}
}
repn(i,m) if(poss[i].size()) solve(i);
repn(i,m) printf("%d\n",ans[i]);
termin();
}