Second My Problem First

Time limit 4000 ms Memory limit 65536 kB

单调队列

来源：
vjudge：B-Second My Problem First
HDU：HDU 3706 Second My Problem First

Description

Give you three integers n, A and B. 
Then we define Si = A^i 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

题意：

其实最开始根本就不懂这个题什么意思，然而找题解的时候都没有说题意！！！都说直接看题就好，意思很好懂，，，我的天哪！！！你自己还是太年轻！！现在来说一下题意：
首先输入会有三个数：n，a，b；
题目的意思是让你最终输出：Ti%b，而Ti是由这句话得到：
    Ti=Min{Sk| i-A<=k<=i,k>=1}
表示的是Sk的最小值，而k的范围是i-A<=k<=i，k给出来的是>=1的，不是需要你去判断它是否>=1！！！是你自己zz了
而Si=A^i%b;
i是从1到n！！！

解题思路：

看懂题之后，就只需要用到单调递减队列来维护一个Si的最大值就好！但是要注意k的范围；

完整代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
using namespace std;
ll q[100010];
ll p[100010];
///用题中的10^7要MLE,改小了数组居然过了，我并不知道why！！！
int main()
{
     ll n,a,b;
     ll s,ans;
     ll head,tail;
     while(scanf("%lld%lld%lld",&n,&a,&b)!=EOF)
     {
         memset(q,0,sizeof(q));
         memset(p,0,sizeof(p));
         s=1,ans=1;
         head=0,tail=0;
         for(int i=1;i<=n;i++)
         {
             s=(s*a)%b;
             while(head<tail&&q[tail-1]>s)///维护题中Ti的最小值;
                tail--;
             q[tail]=s;
             p[tail]=i;
             tail++;
             while(head<tail&&i-a>p[head])///要满足;i-A<=k<=i
                head++;
             ans=(ans*q[head])%b;
         }
         printf("%lld\n",ans);
     }
     return 0;
}