https://ac.nowcoder.com/acm/contest/329/F

题解：

std

本题分为两个子问题。

1. 求一个数组连续p个数mod P的乘积

把序列按照长度m分成若干段，计算每段内的前缀和后缀乘积。
这样任意划窗位置的答案可以看成前一段的后缀和后一段的乘积拼出。
时间复杂度𝑂(𝑛∗𝑚+𝑝−1)

2. 找出长度为k的符合条件的链的个数

使用dfs进行搜索，复杂度〖400∗3〗^20显然会超时，因此使用枚举起点然后双向dfs的方法，一次往两边进行搜索，从而把复杂度降低到400∗〖2∗3〗^10，可以使用状压等方式记录状态。

#include <map>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <string>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define LL long long
#define pi acos(-1)
#define sqr(a) ((a)*(a))
 
using namespace std;
 
int n,k,m,p;
LL a[1000505],b[1000505],ans,X,Y,Z,P,curans;
int mapp[25][25];
int tmp[1048576];
int fx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int nowx,int nowy,int cnt,int res,int tot,bool flag)
{
    if (cnt==tot)
    {
        if (!flag)
            tmp[res>>1]++;
        if (flag)
            ans+=tmp[(((1<<(k+1))-1)^res)>>1];
        return;
    }
    for (int i=0;i<4;i++)
    {
        int nextx=nowx+fx[i][0],nexty=nowy+fx[i][1];
        if (res&(1<<mapp[nextx][nexty])) continue;
        dfs(nextx,nexty,cnt+1,res|(1<<mapp[nextx][nexty]),tot,flag);
    }
}
int main()
{
    int i,j;
    scanf("%d%d%d%lld%d",&n,&m,&p,&P,&k);
    scanf("%lld%lld%lld%lld",&a[0],&X,&Y,&Z);
    //printf("%lld %lld %lld %lld\n",a[0],X,Y,Z);
    for (i=1;i<=n*m+p-1;i++) a[i]=(a[i-1]*a[i-1]%P*X%P+a[i-1]*Y%P+Z)%P;
    //for (i=1;i<=n*m+p-1;i++) printf("%lld ",a[i]);
    //printf("\n");
    j=0;
    int cnt=0;
    for (i=p;i<=n*m+p-1;i++)
    {
        ans=ans*a[i]%P;
        if (i-p+1>j)
        {
            ans=1;
            j=i;
            b[i]=a[i];
            for (int t=i-1;t>=i-p+1;t--) b[t]=b[t+1]*a[t]%P;
        }
        tmp[++cnt]=(LL)b[i-p+1]*ans%P;
    }
    int cur=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            mapp[i][j]=tmp[++cur]%k+1;
            //printf("%d%c",mapp[i][j],j==m?'\n':' ');
        }
    ans=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            memset(tmp,0,sizeof(tmp));
            //tmp[0]=1;
            dfs(i,j,1,1|(1<<mapp[i][j]),k/2,false);
            dfs(i,j,1,1,k/2+k%2+1,true);
        }
    if (n==1&&m==1) ans=1;
    printf("%lld\n",ans);
    return 0;
}