2017 China Collegiate Programming Contest

题目链接：http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf
总结：
上来是俩水题，然后接着看B，C题其实都是思维水题。
B题不需要推公式，dfs可以直接卡过，C题手动模拟出结论？
不过暴露出来了我对博弈的有点遗忘和数学公式推理薄弱。确实好久没见过了，为了避免以后碰到凉凉，还是有必要认真重新复习下。
B.Master of Phi
比赛的时候写了一发dfs超时。但复杂度好像能过，重写了一下：(注意：预处理，以及dfs求所有组合)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int p[25], q[25], m;
inline int q_pow(int a, int b){
    int ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int n, res, A[25];
inline void dfs(int u, int tmp)
{
    if(u == m + 1)
    {
        res = (res + tmp)%mod;
        return ;
    }
    dfs(u + 1, tmp * A[u] % mod);
    dfs(u + 1, tmp);
}

signed main()
{
    int t;
    cin >> t;
    while(t--)
    {
        res = 0;
        n = 1;
        cin >> m;
        for(int i = 1; i <= m; i++){
            cin >> p[i] >> q[i];
            A[i] = q[i] * (p[i] - 1) % mod * q_pow(p[i], mod-2) % mod;
            n = n * q_pow(p[i], q[i]) % mod;
        }

        dfs(1, 1);
        cout << res*n % mod << endl;
    }
}

但是这道题是一道利用积性函数性质和欧拉函数性质的好题
积性函数：https://baike.baidu.com/item/%E7%A7%AF%E6%80%A7%E5%87%BD%E6%95%B0/8354949?fr=aladdin
欧拉函数：https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0
推公式即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int p[25], q[25];
int q_pow(int a, int b){
    int ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1; 
    } 
    return ans;
}
signed main()
{
    int t; cin >> t;
    while(t--)
    {
        int m, ans = 1; 
        cin >> m;
        for(int i = 1; i <= m; i++) {
            cin >> p[i] >> q[i];
            int tmp = q_pow(p[i], q[i]) * ((1 + q[i] - (q[i] * q_pow(p[i], mod-2) % mod) + mod) % mod) % mod;
            ans = ans * tmp % mod;
        }
        cout << ans << endl;
    }
}

C(博弈).
n个堆的取石子游戏，要求每个回合Hakase取两次， Nano取1次。
思路:
1.Hakase先手，从特殊角度思考，如果全是1怎么办？手动模拟发现如果有n堆石子，n个1，若3|n则Hakase输掉游戏，其他情况Hakase必赢。除了刚刚说的那种情况，尝试不利于Hakase构造任何一种最终状态之前的状态，会发现Hakase总能获胜。
2，首先由1可知，如果3|n在Hakase先手的时候输掉游戏，那里要求n个包都是1，只需要让一个包变成不为1的数，Nano先手让这个包变成1即可。如果现在都是1，我们再次手动模拟发现如果n%3=1都是Nano赢，并且由于Nano先手，其实如果Nano第一次要取的那个包如果有多于1的石子也是可以的。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, d;
        cin >> n >> d;
        int cnt = 0;
        for(int i = 1, x; i <= n; i++) {
            cin >> x;
            if(x == 1) ++cnt;
        }
        if(d == 1)
        {
            if(cnt == n && n % 3 == 0)
            {
                cout << "No" << endl;
            }
            else cout << "Yes" << endl;
        }
        else
        {
            if(cnt == n && n % 3 == 1)
            {
                cout << "No" << endl;
            }
            else if(cnt == n-1 && n % 3 == 1)
            {
                cout << "No" << endl;
            }
            else if(cnt == n-1 && n % 3 == 0)
            {
                cout << "No" << endl;
            }
            else
            {
                cout << "Yes" << endl;
            }
        }
    }
}