本文主要是介绍处女座和小姐姐（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
课上处女座成功将纸条传给了小姐姐，约下午和小姐姐一起逛街。他们坐在公交车上一起欣赏窗外的广告牌，每一个广告牌都有一个编号，而处女座的视野范围是有限的，每次只能看到连续的p个广告牌。由于处女座是数学大师，他用O(1)的时间算出来了他看到的广告牌编号的积mod P的值并记录了下来，直到坐车到了商场。
商场里有定制手环的地方，他可以定制一个长度为k的手环，但是选号是收费的，而处女座把家教挣来的钱都用于外出打比赛了，于是他决定自己挑号。
他把之前路上记下来数字按先从左往右，再从上到下的顺序排成一个n*m的矩阵，他想从中选出一条长度为k的路径，使得路径上的数在mod k的意义上各不相同（每个点只和他的上下左右相邻），从而作为他选的号码。
现在处女座想知道，他有多少条路径可以选择（不忽视顺序，(2,2)->(2,1)和(2,1)->(2,2)会被视为两条路径）。
【输入描述】
输入数据共包括两行，第一行包括四个整数n,m,p,P,k，其中p为处女座一次能看到的连续广告牌的数量，其他字母含义如描述所示。
第二行包括四个整数a0,x,y,z，对于每个广告牌而言，他的编号是ai=x∗ai−12+y∗ai−1+z。广告牌从a1开始到an∗m+p−1为止。
1≤n,m≤20
1≤k≤min(20,n∗m)
1≤p≤106
1≤A0,P,X,Y,Z≤1,000,000,000【输出描述】
一个整数，表示可以选择的路径数量。
【样例】
示例1
输入
2 2 1 2 2
1 0 1 1
输出
4
说明
a1=2,a2=3,a3=4,a4=5所以2*2的矩阵是：
0 1
0 1
因此可行方案有(1,1)->(1,2),(1,2)->(1,1),(2,1)->(2,2),(2,2)->(2,1)共4种
思路：
问题可以分成两个子问题，首先是求一个数组连续 p 个数 mod p 的乘积，其次是找出长度为 k 的符合条件的链的个数
对于第一个问题，可以将序列按照长度 m 进行分段，每段分别计算前缀和后缀乘积，这样任意位置的答案可以看成前段的后缀与后短的乘积拼出
对于第二个问题，可以用 dfs 进行搜索，但由于 (400*3)^20 显然会 TLE，因此可进行双向优化，枚举起点然后双向 dfs，一次向两边进行搜索，故而时间复杂度可降到 400*(2*3)^10，此外，可以使用状压的方式来记录状态
【源代码】
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-6
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define N 2000001
#define LL long long
using namespace std;
LL n,m,p,P,k;
LL a[N],b[N],temp[N];
LL X,Y,Z;
LL res;
LL G[101][101];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void dfs(int x,int y,int cnt,int ans,int sum,bool flag)
{if(cnt==sum){if(!flag)temp[ans>>1]++;if(flag)res+=temp[(((1<<(k+1))-1)^ans)>>1];return;}for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(ans&(1<<G[nx][ny]))continue;dfs(nx,ny,cnt+1,ans|(1<<G[nx][ny]),sum,flag);}
}
int main(){scanf("%lld%lld%lld%lld%lld",&n,&m,&p,&P,&k);scanf("%lld%lld%lld%lld",&a[0],&X,&Y,&Z);for(int 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;int cnt=0;//标号int pos=0;//位置for(int i=p;i<=n*m+p-1;i++){//后缀res=res*a[i]%P;if(i-p+1>pos){res=1;pos=i;b[i]=a[i];for(int j=i-1;j>=i-p+1;j--)b[j]=b[j+1]*a[j]%P;}temp[++cnt]=(LL)b[i-p+1]*res%P;}int cur=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)G[i][j]=temp[++cur]%k+1;res=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){memset(temp,0,sizeof(temp));//双向优化搜索dfs(i,j,1,1|(1<<G[i][j]),k/2,false);dfs(i,j,1,1,k/2+k%2+1,true);}}if(n==1&&m==1)res=1;printf("%lld\n",res);return 0;
}
这篇关于处女座和小姐姐（二）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
