A. Shockers

根据题意大力模拟即可。

然而我有一处 -'a' 写成了 -'0' 调了很久。。

B. Seating of Students

构造题。

若 n,m 中有一个 \geq 4（不妨假设 m\geq 4），考虑每行的元素顺序。对于 m>4 时容易得到构造：

1 3 5 ... ((m+1)/2)*2-1 2 4 6 ... (m/2)*2
2 4 6 ... (m/2)*2       1 3 5 ... ((m+1)/2)*2-1
1 3 5 ... ((m+1)/2)*2-1 2 4 6 ... (m/2)*2
2 4 6 ... (m/2)*2       1 3 5 ... ((m+1)/2)*2-1
...

当 m=4 时特殊构造：

2 4 1 3
3 1 4 2
2 4 1 3
3 1 4 2
...

即可。若 n,m\leq 3 则暴力计算。

实际 n,m\leq 3 时只有 n=3,m=3 时成立，人类智慧手算也可。

我做这道题的时候因为行和列间的转换做的不对 WA 了几次。

C. Party

题意的目的是将原图转化为一个完全图。

考虑对一个点的操作，相当于合并包含它的所有团。实际做的时候，只用考虑它所在的其中一个团，并合并它所有出边连向的点即可。为此，我们做状压 DP，设 f(s) 表示点集 s 被转化为完全图的最小步数。初值把原图的所有完全子图赋为 0，刷表即可转移。顺便记一下每个状态的前驱状态，方便输出方案。时间复杂度 O(n2^n)。代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=23;
const int MAXS=5000000;
int e[MAXN], f[MAXS];
pair<int, int> p[MAXS];
void solve(int s)
{
    if (p[s].second==0) return;
    solve(p[s].first);
    printf("%d ", p[s].second);
}
int main()
{
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i=1; i<=m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u-1]|=1<<v-1; e[v-1]|=1<<u-1;
    }
    for (int i=0; i<n; i++) e[i]|=1<<i;
    memset(f, 0X3F, sizeof f);
    for (int s=0; s<1<<n; s++)
    {
        int t=s;
        for (int i=0; i<n; i++)
            if (s&1<<i) t&=e[i];
        if (t==s) f[s]=0, p[s].second=0;
        for (int i=0; i<n; i++)
            if (s&1<<i&&f[s]+1<f[s|e[i]])
            {
                f[s|e[i]]=f[s]+1;
                p[s|e[i]]=make_pair(s, i+1);
            }
    }
    printf("%d\n", f[(1<<n)-1]);
    solve((1<<n)-1);
    putchar('\n');
    return 0;
}

D. Power Tower

前置知识：扩展欧拉定理。

以上。

以及欧拉函数的一个性质：记 \varphi^k(n) 为欧拉函数的 n 次复合，则最小的 k 使 \varphi^k(n)=1 为 O(\log n)。

对于式子 ，这是一个嵌套的形式，我们可以从外到内迭代。最外层（第 0 层）的模数是 m，第 1 层的模数是 \varphi(m)，……，第 k 层的模数为 \varphi^k(m)。根据上述性质可知迭代 O(\log m) 层后模数会变为 1，这使答案为 0，因此对答案有影响的只有前几层。套用扩展欧拉定理，并同时维护答案是否小于当前模数即可。

设当前区间为 [l,r]，模数为 p，则具体的过程可以这样处理：

• 若 p=1，此时答案为 0，不小于当前模数；
• 否则若 l>r 或 w_l=1，此时答案为 1，小于当前模数；
• 否则，迭代进入下一层，
  • 若下一层的答案 r<\varphi(p)，快速幂计算 w_l^{r}\bmod p 即为答案，并暴算 w_l^r 是否小于 p ；
  • 若下一层的答案 r\geq\varphi(p)，快速幂计算 w_l^{r\bmod\varphi(p)\;+\;\varphi(p)} 即为答案，容易观察到上式一定不小于 p。

复杂度为 O(n\log^2p)。下面是代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=110000;
const int MAXK=100;
int qpow(int n, int k, int p)
{
    int r=1;
    while (k)
    {
        if (k&1) r=1ll*r*n%p;
        n=1ll*n*n%p; k>>=1; 
    }
    return r;
}
int calc_phi(int n)
{
    int res=n;
    for (int i=2; i*i<=n; i++)
        if (n%i==0)
        {
            res=res/i*(i-1);
            while (n%i==0) n/=i;
        }
    if (n>1) res=res/n*(n-1);
    return res;
}
int n, m, q, a[MAXN];
int k, phim[MAXK];
pair<int, bool> query(int l, int r, int p)
{
    if (p==k) return make_pair(0, 0);
    if (l>r||a[l]==1) return make_pair(1, 1);
    auto t=query(l+1, r, p+1);
    if (t.second)
    {
        int r=1; bool flag=1;
        for (int i=1; i<=t.first; i++)
        {
            if (1ll*r*a[l]>=phim[p]) { flag=0; break; }
            r*=a[l];
        }   
        return make_pair(qpow(a[l], t.first, phim[p]), flag);
    }
    return make_pair(qpow(a[l], t.first+phim[p+1], phim[p]), 0);
}
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    phim[0]=m;
    while (phim[k]!=1)
        k++, phim[k]=calc_phi(phim[k-1]);
    scanf("%d", &q);
    while (q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r, 0).first);
    }
    return 0;
}