題意：
解釋題意不如直接把這個題粘貼過來，因為題目很短題意很容易懂。
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


思路：
? ? ? 比較簡單的一個單調隊列題目，我們可以建立一個單調遞增的單調隊列，開一個1000W的數組，不用怕報內存，內存夠，然后我們每次都把一個新值進隊列，然后把隊尾比這個值大于等于的出隊，對頭把下標之差大于A的出隊就行了，每次都是把一個新的值放進隊列，然后在對頭拿一個最小的來作為當前的T,然后一邊更新，一邊拿，一邊記錄答案就行了，O(n)的時間復雜度，1000W的，可以過（不過感覺還是有點險，但這個題目都O(n)了在過不了，那估計就設計到轉換什么的了，那我就做不了了，嘿嘿）。


#include<stdio.h>
#include<string.h>

#define N 10000005

typedef struct
{
? ?int id;
? ?__int64 num;
}NODE;

NODE Q[N];
int tou ,wei;
__int64 A ,B ,n;

void insert(int id ,__int64 num)
{
? ?for(int i = wei ;i > tou ;i --)
? ?{
? ? ? if(Q[wei].num >= num) wei --;
? ? ? else break;
? ?}
? ?Q[++wei].num = num;
? ?Q[wei].id = id;
? ?for(int i = tou + 1 ;i <= wei ;i ++)
? ?if(id - Q[i].id > A) tou ++;
? ?else break;
}

int main ()
{
? ?while(~scanf("%d %I64d %I64d" ,&n ,&A ,&B))
? ?{
? ? ? __int64 now = A % B;
? ? ? __int64 Ans = 1;
? ? ? tou = wei = 0;
? ? ? for(int i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?insert(i ,now);
? ? ? ? ?Ans = (Ans * Q[tou+1].num) % B;
? ? ? ? ?now = now * A % B;
? ? ? }
? ? ? printf("%I64d\n" ,Ans);
? ?}
? ?return 0;
}
? ? ? ? ?



《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的hdu3706基础的单调队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。