前言：

感觉是先天caibi圣体，每次准备好好的打，就被狠狠卡住里，幸好最后比赛unrated了，不然直接掉打分，唉，要是掉了不知道多久能回来，唉。补题了

A.Cidoai的幂次序列

题目方程乍一看很唬人，实际上带一下样例就会明白怎么回事

2244 = pow(2,3) + pow(3,7) +pow(7,2)

恰好就是一个循环，妙！

那就直接输入1和n-1就行了（也就会这一点了）

void solve(){
    LL n,k;
    cin>>n>>k;
    cout<<2<<endl;
    cout<<1<<" "<<n-1<<endl;
}

B Cidoai的平均数对

直接在这里卡到爆，一直在想什么背包有关平均值，不知道怎么处理平均，赛后看群里大佬提了一嘴，就是化把所有容积减去k这个数，就转化成保证容积为0的01背包，看完想了一下，几分钟就把题a掉了（思路没想到，还是练少了。。。）

先把负的贪心进去，再累计转为背包容积，然后把正的往里狠狠地塞就行了

int main() {
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1,0),b(n+1,0),dp(250000,0);
    int cnt = 0;
    int ans = 0;
    int num = 0;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        b[i]-=k;
        if(b[i]<=0) {
            cnt++;
            num+=abs(b[i]);
            ans+=a[i];
        }
    }
    int op = 0;
    vector<int> c(n+1,0),d(n+1,0);
    for(int i=1;i<=n;i++){
        if(b[i]>0){
            c[++op]=a[i];
            d[op]=b[i];
        }
    }
    for(int i=1;i<=op;i++){
        for(int j = num;j>=d[i];j--){
            dp[j] = max(dp[j] , dp[j-d[i]]+c[i]);
        }
    }
    cout<<dp[num]+ans;

}

C Cidoai的树上方案

重点还是状态转移方程的书写，还有题意的理解 dp设置01状态来转移

对于每个点，都要赋初值1，用不用都算一种情况，最后算的时候要乘起来，因为孩子都是可以使用，之间是乘的关系

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int p = 998244353;
const int N = 2e6 + 10;
vector<LL> a(N, 0);
vector<LL> g[N];
vector<vector<LL>> dp(N, vector<LL>(2, 0));
LL res = 1 ,ans = 1;
void dfs(int x) {
    dp[x][0] = 1;
    dp[x][1] = 1;
    for (int i = 0; i < g[x].size(); i++) {
        int son = g[x][i];
        dfs(son);
        dp[x][0] = (dp[x][0]%p*(dp[son][0]+dp[son][1])%p)%p;
        dp[x][1] = ((dp[x][1]%p)*(dp[son][0]%p))%p;
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <=n; i++) {
        cin >> a[i];
        g[a[i]].push_back(i);
    }
    dfs(1);
    cout << (dp[1][1]+dp[1][0])%p << endl;  
    
    return 0;
}