【题目链接】点击打开链接

【题意】非常简单，题目很短，自己读一下就好。

【解题思路】 单调队列的应用，维护一个递增的长度为A的单调队列了可以了。但是这题用数组的话，会MLE，反正我是被卡MLE了。所以改用STL的deque实现，可以解决本题。

【AC代码】


//
//Created by just_sort 2016/1/7
//Copyright (c) 2016 just_sort.All Rights Reserved
//

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
const int maxn = 5000010;
const int maxm = 2e5;
const int maxs = 10;
const int maxp = 1e3 + 10;
//const int INF  = 1e9;
const int UNF  = -1e9;
//const int mod  = 1e9 + 7;
int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head

//struct node{
//    LL v;
//    int pos;
//    node(){}
//    node(LL v, int pos) : v(v), pos(pos) {}
//}que1[maxn];
//int head1, tail1;
//int n;
//LL A, B;
//LL powmod(LL a, LL n, LL mod)
//{
//    LL res = 1;
//    while(n)
//    {
//        if(n & 1) res = res * a % mod;
//        a = a * a % mod;
//        n >>= 1;
//    }
//    return res;
//}
//int main()
//{
//    while(scanf("%d%I64d%I64d", &n, &A, &B) != EOF)
//    {
//        memset(que1, 0, sizeof(que1));
//        head1 = tail1 = 0;
//        LL ans = 1, x = 1;
//        REP1(i, 0, n)
//        {
//            x = (x * A) % B;
//            while(head1 < tail1 && 1LL*(i - que1[i].pos) > A) ++head1;
//            while(head1 < tail1 && que1[tail1 - 1].v >= x) --tail1;
//            que1[tail1] = node(x, i);
//            tail1++;
//            ans = ((ans % B) * (que1[head1].v % B)) % B;
//        }
//        printf("%I64d\n", ans);
//    }
//    return 0;
//}

LL n, a, b;
deque <pair <int, int> > q;

int main()
{
    while(cin >> n >> a >> b)
    {
        q.clear();
        LL ans = 1, x = 1;
        REP2(i, 1, n){
            x = x * a % b;
            while(!q.empty() && i - q.front().first > a) q.pop_front();
            while(!q.empty() && q.back().second >= x) q.pop_back();
            q.push_back(MP(i, x));
            ans = ans * q.front().second % b;
        }
        cout << ans << endl;
    }
    return 0;
}

其中注释掉的是被卡MLE得部分。