Problem Description

Give you three integers n, A and B. 
Then we define S_i = Aⁱ mod B and T_i = Min{ S_k | i-A <= k <= i, k >= 1}
Your task is to calculate the product of T_i (1 <= i <= n) mod B.

 

   不描述题意了，三行英文挺明了的，今天刚学单调队列，自己模拟一下过了这题

   单调队列

   1，永远保持队首元素为最小值。

   2，插入时，先将队尾大于插入值的元素删去

   3，保证队首元素一直是合法，所需元素。

  代码

  #include<stdio.h>
#include<math.h>
int tou, wei, count;
struct cc
{
   __int64 value;
   int num;       
}mark[10000005];
void add ( int x ,int k)
{
  if(k == 1)  return;


  if( tou == wei )  {mark[tou].value = http://www.mamicode.com/x; mark[wei].num = k; return;}
  if(mark[tou].value > x) {mark[tou].value = http://www.mamicode.com/x; mark[tou].num = k; wei = tou+1; return;}
  for(int i = wei - 1; i >= tou; i--) 
  {
     if(mark[i].value <= x)
     {
      mark[i+1].value = http://www.mamicode.com/x;
      mark[i+1].num = k;
      wei = i + 2;
      break;
     }
  }      
  for(int i = tou; i < wei; i++)
  {
     if(mark[i].num < count)
     {
      tou++;              
     }      
     else break; 
  }
}
int main()
{
  int n, a, b;
  __int64 k;
  __int64 sum, ji;
  while(scanf("%d%d%d", &n, &a, &b) != EOF)
  {
    count = -1, ji = 1;
    mark[0].value = http://www.mamicode.com/a % b;
    mark[0].num = 1;
    tou = 0, wei = 1, k = 1;
    for(int i = 1; i <= n; i++)
    {
      k = k * a % b;
      count = i - a;
      add(k, i); 
      ji *= mark[tou].value;
      if( ji >= b ) ji %= b;      
    }     
    printf("%I64d\n", ji); 
  }      
}