题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=3706 【原题】 Second My Problem First
Time Limit: 12000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1955 Accepted Submission(s): 743
Problem Description Give you three integers n, A and B. Then we define Si = Ai mod B and Ti = Min{ Sk | i-A <= k <= i, k >= 1} Your task is to calculate the product of Ti (1 <= i <= n) mod B.
Input Each line will contain three integers n(1 <= n <= 107),A and B(1 <= A, B <= 231-1). Process to end of file.
Output For each case, output the answer in a single line.
Sample Input 1 2 3 2 3 4 3 4 5 4 5 6 5 6 7
Sample Output 2 3 4 5 6
Author WhereIsHeroFrom@HDU 【中文题意】 给你三个整数n,A,B。让你求出T[i]之积，1<=i<=n,T[i]是这么求的，T[i]=min(s[i-A]~s[i])，s[i]=A^i。 反正怎么看原文怎么感觉别扭。 【思路分析】 首先s[i]是很好求的，然后我们看n的数据范围，10^7，灰常大啊，这个时候我们只能考虑线性的做法，虽然rmq区间最小值查询的时间复杂度为O(nlog(n))，但是对这个题行不通….所以我们只能用单调队列来维护区间最小值，时间复杂度为O(n)。另外一个比较烦人的地方是这个题卡内存，用long long 数组的话是爆内存的，所以只能使用int 。 【AC代码】
#include<stdio.h> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #define MAX_N 10000005 #define LL long long LL n,A,B; int ss[MAX_N]; int deq[MAX_N];//双端队列 存储的是ss数组中元素的位置 void solve() { int s=0,t=0;//双端队列的头部和尾部 long long re=1; ss[0]=1; for (int i=1; i<=n; i++) { ss[i] = (int)(((long long)ss[i-1] * A) % B); } for(int i=1; i<=n; i++) { while(s<t&&deq[s]<i-A) s++; while(s<t&&ss[deq[t-1]] >= ss[i]) t--;//双端队列的尾部一直大于当前值，需要不断删除尾部 deq[t++]=i; //printf("deq[s]= %lld\n",deq[s]); re*=(long long)ss[deq[s]]; re%=B; } printf("%lld\n",re); } int main() { while(~scanf("%lld %lld %lld",&n,&A,&B)) { solve(); } return 0; }