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.
用單調隊列來維護最小值即可
1
//file name:1007.c
2//author:yzhw_ujs
3//problem: hdu contest 10.30 1007
4//method 單調隊列+線掃
5
6
7# include <stdio.h>
8struct node
9
{
10
int pos,value;
11
}q[10000005];
12int s,e;
13int main()
14{
15 int n,a,b;
16 while(scanf("%d%d%d",&n,&a,&b)!=EOF)
17
{
18 int total=a%b,t=a%b,i;
19 s=e=-1;
20 e++;
21 q[e].pos=1;
22 q[e].value=t;
23 for(i=2;i<=n;i++)
24 {
25 t=((long long)t*(a%b))%b;
26 while(e!=s&&q[e].value>=t) e--;
27 q[++e].pos=i;
28 q[e].value=t;
29 while(s!=e&&q[s+1].pos<i-a) s++;
30 total=((long long)total*(q[s+1].value%b))%b;
31
}
32 printf("%d\n",total);
33 }
34 return 0;
35}
36