A.矩阵

​ hash好题啊，一眼看是二维hash，但我不会。怎么办？

​ 我只好用洛谷子矩阵的思路，先求出每行的hash值， 再每列把行的hash值hash一下。

​ 对于边长，我们采用二分，显然有单调性。矩阵越小越容易判匹配，越大越不容易匹配

​ 时间复杂度n^2log(n)

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N=1005;
const int base=31;
const int base2=127;
int n,m,cnt,l,r,mid,hs3[N],has[N*N],p[N],p2[N],a[N][N],hs[N][N],hs2[N][N];
bool pd(int x)
{
    for(int i=1;i<=n;i++)
        for(int j=x;j<=m;j++)hs2[i][j]=hs[i][j]-hs[i][j-x]*p[x];
    cnt=0;
    for(int j=x;j<=m;j++)
    {
        for(int i=1;i<=n;i++)hs3[i]=hs3[i-1]*base2+hs2[i][j];
        for(int i=x;i<=n;i++)has[++cnt]=hs3[i]-hs3[i-x]*p2[x];
    }
    sort(has+1,has+cnt+1);
    for(int i=2;i<=cnt;i++)
        if(has[i]==has[i-1])return true;
    return false;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    char c[N][N];
    for(int i=1;i<=n;i++)
    {
        scanf("%s",c[i]+1);
        for(int j=1;j<=m;j++)a[i][j]=c[i][j]-'a';
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)hs[i][j]=hs[i][j-1]*base+a[i][j];
    p[0]=1;p2[0]=1;
    for(int i=1;i<=max(n,m);i++)p[i]=p[i-1]*base;
    for(int i=1;i<=max(n,m);i++)p2[i]=p2[i-1]*base2;
    l=0;r=min(n,m);
    while(l<r)
    {
        mid=(l+r+1)/2;
        if(pd(mid))l=mid;
        else r=mid-1;
    }
    cout<<l;
    return 0;
}

B.树

​ 一眼我还以为是树形dp题，后来发现就是简单的一个dp。

​

​ 我们发现对于一个点u，它的颜色不仅取决于他的父亲，还取决于他的兄弟。

​ 我们把树上的点编号，发现第i个点的颜色取决于第i-1个点的颜色。

​ 表示前i个点，用j种颜色的方案数。

​ 时间复杂度nm

​

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
int n,m,ans,f[305][305];
signed main()
{
    scanf("%lld%lld",&n,&m);
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)f[i][j]=(f[i-1][j]+f[i-1][j-1]*(m-j+1)%p)%p;
    for(int i=1;i<=m;i++)ans=(ans+f[n][i])%p;
    cout<<ans;
}

C.圈圈

​ 没有看错，不要怀疑，这又是到hash题

​ 我们发现一旦有数加1模m后等于0，那么以这个数开头的队列就是最小的之一

​ （因为不止有一个数加1模m后等于0）

​ 那判大小怎么解决呢？hash+二分，二分找到lcp，就可以判断大小了。（常规操作）

​ 当然，如果有大佬想用后缀数组或后缀自动机也完全可以

​ 时间复杂度（mlog(n)）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int base=1e9+7;
int n,m,k,l,r,ans,mid,a[N],ha[N],p[N];
vector<int>v[N];
int bj(int x,int y,int add)
{
    l=0;r=n;
    while(l<r)
    {
        mid=(l+r+1)/2;
        if(ha[x+mid-1]-ha[x-1]*p[mid]==ha[y+mid-1]-ha[y-1]*p[mid])l=mid;
        else r=mid-1;
    }
    if(l==n)return x;
    if((a[x+l]+add)%m<=(a[y+l]+add)%m)return x;
    return y;
}
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        v[m-a[i]].push_back(i);
        a[i+n]=a[i];
    }
    for(int i=1;i<=n+n;i++)ha[i]=ha[i-1]*base+a[i];
    p[0]=1;
    for(int i=1;i<=n+n;i++)p[i]=p[i-1]*base;
    ans=1;
    for(int i=2;i<=n;i++)ans=bj(ans,i,0);
    printf("%lld\n",a[ans+k-1]);
    for(int i=1;i<m;i++)
    {
        if(v[i].size())
        {
            ans=v[i][0];
            for(int j=1;j<v[i].size();j++)ans=bj(ans,v[i][j],i);
        }
        printf("%lld\n",(a[ans+k-1]+i)%m);
    }
    return 0;
}