HUD 3706 單調隊列簡單題

HUD 3706 單調隊列簡單題

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
#include
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 = x; mark[wei].num = k; return;}
if(mark[tou].value > x) {mark[tou].value = 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 = 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 = 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);
}
}