# 第三屆科揚盃資訊科 editorial

link: https://hackmd.io/@BaoCoder613/rybj0r-_yx

## pA
純粹暴力求和，求和完判奇偶即可。注意到總和可能達到 $10^{11}$，要開 long long。
預期難度：800*
:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
    int n;
    cin>>n;
    ll tot=0, a;
    for(int i=0; i<n; i++){
        cin>>a;
        tot+=a;
    }
    if(tot%2) cout<<"yes";
    else cout<<"no";
}

:::

## pB
注意到 $f(x)^2=x^2$ 代表 $f(a)\in\{a, -a\}$ 對於任意 $a$ 都成立。因此我們先用一個陣列存每個數字出現幾次，再做位元枚舉。
預期難度：1100*
:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int a[2000005];
vector <int> v;

int main(){
    int n, x;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>x;
        x+=1000000;
        a[x]++;
    }
    for(int i=0; i<=1000000; i++){
        if(a[1000000+i]-a[1000000-i]){
            v.pb(i*(a[1000000+i]-a[1000000-i]));
        }
    }
    n=v.size();
    int sum=0;
    bool solved=false;
    for(int i=0; i<(1<<n); i++){
        sum=0;
        for(int j=0; j<n; j++){
            if(i&(1<<j)) sum+=v[j];
            else sum-=v[j];
        }
        if(!sum){
            solved=true;
            break;
        }
    }
    if(solved) cout<<"yes";
    else cout<<"no";
}

:::

## pC
這題有兩種做法。
做法一：建 DSU，先把沒壞的路連起來。接著把剩餘的邊按照邊權排序，依序檢查，如果兩端點還沒有連通的話，就花費邊權的 cost 把它們用 DSU 連起來。重複直到圖連通為止。(後面其實類似 Kruskal 的做法)
做法二：把沒壞的路邊權都改成$0$，直接找最小生成樹(Kruskal 或 Prim)。

預期難度：1300*
:::spoiler code(做法一)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

struct edge{
    int u, v;
    ll w;
};

bool MySort(edge e1, edge e2){
    return e1.w<e2.w;
}

const int MAXN=100005;
int dsu[MAXN], sz[MAXN];
vector <edge> E;
int cc;

void init(int n){
    for(int i=1; i<=n; i++){
        dsu[i]=i;
        sz[i]=1;
    }
    cc=n;
}

int fa(int a){
    if(dsu[a]==a) return a;
    dsu[a]=fa(dsu[a]);
    return fa(dsu[a]);
}

int A, B;
void join(int a, int b){
    A=fa(a);
    B=fa(b);
    if(A==B) return;
    cc--;
    if(sz[A]>sz[B]){
        dsu[B]=A;
        sz[A]+=sz[B];
    }
    else{
        dsu[A]=B;
        sz[B]+=sz[A];
    }
}

ll ans=0;
void kruskal(){
    sort(E.begin(), E.end(), MySort);
    for(edge e: E){
        if(cc==1) return;
        if(fa(e.u)==fa(e.v)) continue;
        ans+=e.w;
        join(e.u, e.v);
    }
}

int u[200005], v[200005];
ll w[200005];
int brk[200005];

int main(){
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        cin>>u[i]>>v[i]>>w[i];
    }
    init(n);
    int a, k;
    cin>>k;
    for(int i=1; i<=k; i++){
        cin>>a;
        brk[a]=1;
        E.pb({u[a], v[a], w[a]});
    }
    for(int i=1; i<=m; i++){
        if(!brk[i]) join(u[i], v[i]);
    }
    kruskal();
    if(cc>1) cout<<-1;
    else cout<<ans;
}

:::
這題的 code 也滿長的，但也有 59 行的模板。

## pD
計算幾何問題，需要處理線段和點、線段和線段關係。一個簡單的作法是去看該次詢問的線段和幾個點、幾個線段相交 (線段和線段交在頂點，也算相交)

交四個線段：一定有切到(一定交兩個頂點)
交三個線段：如果交兩個頂點，就沒切到。如果交一個頂點，就有切到
交兩個線段：如果交一個頂點，就沒切到。如果交零個頂點，就有切到
剩下情況：要嘛不可能，要嘛沒切到

預期難度：1500*
:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
 
struct pt{
    ll x,y;
    bool operator < (pt b){
        if(x==b.x) return y<b.y;
        return x<b.x;
    }
    bool operator > (pt b){
        if(x==b.x) return y>b.y;
        return x>b.x;
    }
    bool operator == (pt b){
        return ((x==b.x)&(y==b.y));
    }
    pt operator + (pt b){
        return {x+b.x, y+b.y};
    }
    pt operator - (pt b){
        return {x-b.x, y-b.y};
    }
    pt operator * (ll c){
        return {x*c, y*c};
    }
    pt operator / (ll c){
        return {x/c, y/c};
    }
    ll operator * (pt b){
        return x*b.x+y*b.y;
    }
    ll operator ^ (pt b){
        return x*b.y-y*b.x;
    }
};
 
 
int sign(ll x){
    if(x==0) return x;
    if(x<0) return -1;
    return 1;
}
 
bool on (pt a, pt b, pt x){
    ll abx=(a-x)^(b-x), dt=(a-x)*(b-x);
    return ((abx==0)&&(dt<=0));
}
 
int dir(pt a, pt b, pt x){
    ll abx=(a-x)^(b-x);
    return sign(abx);
}
 
bool banana(pt a, pt b, pt c, pt d){
    if(on(a, b, c)||on(a, b, d)) return true;
    if(on(c, d, a)||on(c, d, b)) return true;
    if((dir(a, b, c)!=dir(a, b, d))&&(dir(c, d, a)!=dir(c, d, b))) return true;
    return false;
}
 
int main(){
    pt a, b;
    ll x;
    pt sq[5];
    int q;
    cin>>x>>q;
    sq[0]={x, x};
    sq[1]={-x, x};
    sq[2]={-x, -x};
    sq[3]={x, -x};
    sq[4]={x, x};
    int cnte, cntv, ans=0;
    while(q--){
        cin>>a.x>>a.y>>b.x>>b.y;
        cnte=cntv=0;
        for(int i=0; i<4; i++){
            if(on(a, b, sq[i])) cntv++;
        }
        for(int i=0; i<4; i++){
            if(banana(a, b, sq[i], sq[i+1])) cnte++;
        }
        if(cnte==4) ans++;
        else if(cnte==3){
            if(cntv==1) ans++;
        }
        else if(cnte==2){
            if(cntv==0) ans++;
        }
    }
    cout<<ans;
}

:::
PS: 雖然這題的 code 有 93 行，但是其實前 61 行都是模板。

## pE
這題大野狼要在一個特定的 cost 之內最大化得到的價值，所以是一種背包 DP。可是你會發現這題的小豬會逃跑，付了 cost 不一定拿得到。因此我們必須多加一個維度，考慮第 $i$ 棟房子有沒有被吹倒。
假設 $dp[i][j][0/1]$ 代表考慮前 $i$ 棟房子，目前總花費至多 $j$，第 $i$ 棟房子有/沒有被吹倒，我們會有這些轉移式。

$$dp[i][j][0]=\begin{cases}\max(dp[i-1][j][0], dp[i-1][j][1]), \ d[i-1]\leq j \\
dp[i-1][j][0],\ d[i-1]>j\end{cases}$$
然後當 $d[i-1]\leq j$ 的時候我們有
$$dp[i][j+d[i]][1]=\begin{cases}\max(dp[i-1][j][0], dp[i-1][j][1])+m[i], \ d[i-1]\leq d[i] \\
\max(dp[i-1][j][1]+m[i], dp[i-1][j][0]),\ d[i-1]>d[i]\end{cases}$$

當 $d[i-1]>j$ 的時候我們有
$$dp[i][j+d[i]][1]=\begin{cases}dp[i-1][j][0]+m[i], \ d[i-1]\leq d[i] \\
dp[i-1][j][0],\ d[i-1]>d[i]\end{cases}$$

直接兩層迴圈暴力轉移即可
預期難度：1800*
:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int dp[3005][10005][2], d[3005], m[3005];

int main(){
    int n, D;
    cin>>n>>D;
    for(int i=1; i<=n; i++) cin>>d[i];
    for(int i=1; i<=n; i++) cin>>m[i];
    for(int i=1; i<=n; i++){
        for(int j=D; j>=0; j--){
            if(j>=d[i-1]) dp[i][j][0]=max(dp[i-1][j][0], dp[i-1][j][1]);
            else dp[i][j][0]=dp[i-1][j][0];
            if(j+d[i]>D) continue;
            if(d[i]>d[i-1]){
                if(j>=d[i-1]) dp[i][j+d[i]][1]=max(dp[i-1][j][1], dp[i-1][j][0])+m[i];
                else dp[i][j+d[i]][1]=dp[i-1][j][0]+m[i];
            }
            else{
                if(j>=d[i-1]) dp[i][j+d[i]][1]=max(dp[i-1][j][1]+m[i], dp[i-1][j][0]);
                else dp[i][j+d[i]][1]=dp[i-1][j][0];
            }
        }
    }
    int ans=0;
    for(int i=0; i<=D; i++){
        ans=max(ans, dp[n][i][1]);
        ans=max(ans, dp[n][i][0]);
    }
    cout<<ans;
}

:::

## pF
我們用兩顆懶標線段樹，一顆維護竹、一顆維護藥水。分別需要支援以下操作

竹：區間加值、區間求和、區間求 min
藥水：區間改值、區間求 xor

這樣兩種操作就可以如下處理

第一種：把使用的藥水區間求 xor 算出來之後，把該區間藥水歸零。接著對竹的線段樹區間加值。
第二種：把竹的區間最小值算出來，區間減值(跟加值一樣)。
最後我們可以利用竹的區間加值把所有高度都加一。

預期難度：2000*
:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define lc id*2+1
#define rc id*2+2

const int MAXN=200005;
ll med[MAXN];
ll seg[MAXN*4], mn[MAXN*4], sum[MAXN*4], qz[MAXN*4], qm[MAXN*4];

void pullmed(int id){
    seg[id]=seg[lc]^seg[rc];
}

void pullb(int id){
    mn[id]=min(mn[lc], mn[rc]);
    sum[id]=sum[lc]+sum[rc];
}

void pushmed(int id){
    if(!qz[id]) return;
    seg[lc]=0;
    qz[lc]=1;
    seg[rc]=0;
    qz[rc]=1;
    qz[id]=0;
}

void pushb(int id, int l, int r){
    if(!qm[id]) return;
    int m=(l+r)>>1;
    mn[lc]+=qm[id];
    qm[lc]+=qm[id];
    sum[lc]+=qm[id]*(m-l+1);
    mn[rc]+=qm[id];
    qm[rc]+=qm[id];
    sum[rc]+=qm[id]*(r-m);
    qm[id]=0;
}

void buildmed(int id, int l, int r){
    if(l==r){
        seg[id]=med[l];
        return;
    }
    int m=(l+r)>>1;
    buildmed(lc, l, m);
    buildmed(rc, m+1, r);
    pullmed(id);
}

void xormed(int id, int l, int r, int L, int R){
    if(l>=L&&r<=R){
        seg[id]=0;
        qz[id]=1;
        return;
    }
    pushmed(id);
    int m=(l+r)>>1;
    if(L<=m) xormed(lc, l, m, L, R);
    if(R>m) xormed(rc, m+1, r, L, R);
    pullmed(id);
}

void addb(int id, int l, int r, int L, int R, ll val){
    if(l>=L&&r<=R){
        mn[id]+=val;
        sum[id]+=val*(r-l+1);
        qm[id]+=val;
        return;
    }
    pushb(id, l, r);
    int m=(l+r)>>1;
    if(L<=m) addb(lc, l, m, L, R, val);
    if(R>m) addb(rc, m+1, r, L, R, val);
    pullb(id);
}

ll querymed(int id, int l, int r, int L, int R){
    if(l>=L&&r<=R) return seg[id];
    pushmed(id);
    int m=(l+r)>>1;
    ll res=0;
    if(L<=m) res^=querymed(lc, l, m, L, R);
    if(R>m) res^=querymed(rc, m+1, r, L, R);
    return res;
}

ll queryb(int id, int l, int r, int L, int R, int type){
    if(l>=L&&r<=R){
        if(type==0) return mn[id];
        else return sum[id];
    }
    pushb(id, l, r);
    int m=(l+r)>>1;
    ll res;
    if(type==0) res=9e18;
    else res=0;
    if(L<=m){
        if(type==0) res=min(res, queryb(lc, l, m, L, R, 0));
        else res+=queryb(lc, l, m, L, R, 1);
    }
    if(R>m){
        if(type==0) res=min(res, queryb(rc, m+1, r, L, R, 0));
        else res+=queryb(rc, m+1, r, L, R, 1);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k, q;
    cin>>n>>k>>q;
    for(int i=1; i<=k; i++){
        cin>>med[i];
    }
    buildmed(0, 1, k);
    int type, l1, r1, l2, r2;
    ll temp, mins, ans;
    while(q--){
        cin>>type;
        if(type==1){
            cin>>l1>>r1>>l2>>r2;
            temp=querymed(0, 1, k, l2, r2);
            xormed(0, 1, k, l2, r2);
            addb(0, 1, n, l1, r1, temp);
        }
        else{
            cin>>l1>>r1;
            ans=queryb(0, 1, n, l1, r1, 1);
            cout<<ans<<'\n';
            mins=queryb(0, 1, n, l1, r1, 0);
            addb(0, 1, n, l1, r1, -mins);
        }
        addb(0, 1, n, 1, n, 1);
    }
}

:::
這題是那種不用想的題目，完全考驗寫線段樹的能力。

## pG
先觀察到
$$\sum_{j=1}^nd(i, j)\times (a_i^2+a_j^2)=a_i^2\sum_{j=1}^nd(i, j)+2a_i\sum_{j=1}^nd(i, j)\times a_j+\sum_{j=1}^nd(i, j)\times a_j^2$$

考慮換根 DP。先定義後面三項分別是$dsq[i], dsl[i], ds[i]$，並且定義 $i$ 的子樹大小，子樹點權和，子樹點權平方和分別是 $sz[i], as[i], sqs[i]$。則對於某個節點 $cur$ 的子結點 $nxt$ 有以下轉移式
$$ds[nxt]=ds[cur]+sz[1]-(2*sz[nxt])$$
$$dsl[nxt]=dsl[cur]+as[1]-(2*as[nxt])$$
$$dsq[nxt]=dsq[cur]+sqs[1]-(2*sqs[nxt])$$
而節點 $i$ 最終的答案就是
$$a[i]^2\times ds[i]+2\times a[i]\times dsl[i]+dsq[i]$$

預期難度：2100*
:::spoiler

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int MAXN=200005;
ll mod=998244353;
vector <int> G[MAXN];
ll dep[MAXN], a[MAXN], sq[MAXN], sz[MAXN], as[MAXN], sqs[MAXN];
ll ds[MAXN], dsl[MAXN], dsq[MAXN];

void dfspre(int cur, int lst){
    sz[cur]=1;
    as[cur]=a[cur];
    sqs[cur]=sq[cur];
    dep[cur]=dep[lst]+1;
    for(int nxt: G[cur]){
        if(nxt==lst) continue;
        dfspre(nxt, cur);
        sz[cur]+=sz[nxt];
        if(sz[cur]>=mod) sz[cur]-=mod;
        as[cur]+=as[nxt];
        if(as[cur]>=mod) as[cur]-=mod;
        sqs[cur]+=sqs[nxt];
        if(sqs[cur]>=mod) sqs[cur]-=mod;
    }
}

void dfsfin(int cur, int lst){
    for(int nxt: G[cur]){
        if(nxt==lst) continue;
        ds[nxt]=ds[cur]+sz[1]-(2*sz[nxt]);
        ds[nxt]%=mod;
        if(ds[nxt]<0) ds[nxt]+=mod;
        dsl[nxt]=dsl[cur]+as[1]-(2*as[nxt]);
        dsl[nxt]%=mod;
        if(dsl[nxt]<0) dsl[nxt]+=mod;
        dsq[nxt]=dsq[cur]+sqs[1]-(2*sqs[nxt]);
        dsq[nxt]%=mod;
        if(dsq[nxt]<0) dsq[nxt]+=mod;
        dfsfin(nxt, cur);
    }
}

int main(){
    int n;
    cin>>n;
    int v;
    for(int i=2; i<=n; i++){
        cin>>v;
        G[v].pb(i);
        G[i].pb(v);
    }
    for(int i=1; i<=n; i++){
        cin>>a[i];
        sq[i]=(a[i]*a[i])%mod;
    }
    dep[0]=-1;
    dfspre(1, 0);
    for(int i=1; i<=n; i++){
        ds[1]+=dep[i];
        ds[1]%=mod;
        dsl[1]+=dep[i]*a[i];
        dsl[1]%=mod;
        dsq[1]+=dep[i]*sq[i];
        dsq[1]%=mod;
    }
    dfsfin(1, 0);
    ll ans;
    for(int i=1; i<=n; i++){
        ans=a[i]*ds[i];
        ans%=mod;
        ans*=a[i];
        ans%=mod;
        ans+=(2*a[i]*dsl[i]);
        ans%=mod;
        ans+=dsq[i];
        ans%=mod;
        cout<<ans<<" ";
    }
}

:::

## pH
定義 $pf[i]$ 為 $s$ 到第 $i$ 個字元的前綴，而 $pf'[i]$ 為 $s'$ 到第 $i$ 個字元的前綴 (其中 $s'$ 代表把 $s$ 中沒開的店改成 $。
注意到如果大食客 $i$ 在城市 $j$ 會付他吃的前 $k$ 家店的錢，代表 $pf[i]$ 跟 $pf'[j]$ 的後綴長度至少為 $k$，而且 $pf[i]$ 長度為 $k$ 的後綴同時為其前綴。

因此我們將考慮 $s$ 的失配樹，其中 $i$ 的父節點為 $\pi[i]$。如果沒有關門的店，那其實大食客 $i$ 在城市 $j$ 付的錢就會是從 $LCA(i, j)$ 吃到 $1$ 的錢。

注意到如果今天 $j<k$，則第 $i$ 個人會付 $LCA(i, j)$ 吃到 $1$ 的錢，但如果 $j>k$，第 $i$ 個人只會付 $LCA(i, \pi[j])$ 吃到 $1$ 的錢。如果 $j=k$ 那沒有人會付半毛錢。這怎麼處理呢？

考慮對 $s+\#+s'$ 字串做 KMP，假設這個新字串的失配函數為 $\pi'$。那麼我們只要查詢 $LCA(i, \pi'[j+n])$吃到 $1$ 的錢就好了($+n$ 是因為 $s'$ 字串在後方)。我們可以建立花費的前綴和 $pre$ 來加速。於是，我們會需要快速的處理這個函數的查詢
$$f(i)=\sum_{j=1}^n pre[LCA(i, j)]$$

我們考慮換根 DP。先預處理每個節點的子樹大小 $sz$。注意到如果 $v$ 是 $u$ 的子節點，那麼對於 $v$ 的子樹內的任意節點 $w$，$LCA(v, w)\neq LCA(u, w)$。其餘的 LCA 則不變。因此我們有以下轉移式。
$$f(v)=f(u)-(pre[u]\times sz[v])+(pre[v]\times sz[v])$$

最後我們從 $i=n+1$ 到 $i=2n$，分別回答 $f(\pi'[i])$ 即可。(當然也可以像下面的 code 一樣分 case 輸出)

預期難度：2400*
:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int MAXN=1000005;
char s[MAXN*2];
int pi[MAXN*2];
ll pre[MAXN], sz[MAXN], dp[MAXN], a[26];
vector <int> G[MAXN];

void dfspre(int cur, int lst){
    sz[cur]=1;
    for(int nxt: G[cur]){
        if(nxt==lst) continue;
        dfspre(nxt, cur);
        sz[cur]+=sz[nxt];
    }
}

void dfs(int cur, int lst){
    dp[cur]=dp[lst];
    dp[cur]-=pre[lst]*sz[cur];
    dp[cur]+=pre[cur]*sz[cur];
    for(int nxt: G[cur]){
        if(nxt==lst) continue;
        dfs(nxt, cur);
    }
}

int main(){
    int n, k;
    cin>>n>>k;
    string ss;
    cin>>ss;
    for(int i=0; i<n; i++) s[i]=ss[i];
    s[n]='#';
    for(int i=n+1; i<=2*n; i++){
        s[i]=ss[i-n-1];
    }
    s[k+n]='$';
    for(int i=0; i<26; i++) cin>>a[i];
    int j=0;
    for(int i=1; i<=2*n; i++){
        while(j>0 && s[i]!=s[j]) j=pi[j-1];
        if(s[i]==s[j]) j++;
        pi[i]=j;
    }
    for(int i=n; i>=1; i--){
        pi[i]=pi[i-1];
        G[i].pb(pi[i]);
        G[pi[i]].pb(i);
    }
    for(int i=1; i<=n; i++){
        pre[i]=pre[i-1]+a[s[i-1]-'a'];
    }
    dfspre(0, 0);
    dfs(0, 0);
    for(int i=n+1; i<=2*n; i++){
        if(i<n+k) cout<<dp[i-n];
        else cout<<dp[pi[i]];
        cout<<" ";
    }
}

:::

## pI

我們先定義 order 和原根

:::info
對於一個正整數 $n$ 以及一個與 $n$ 互質的整數 $a$，定義$\text{ord}_n(a)$ 為最小的正整數 $k$ 使得 $a^k\equiv 1\pmod{p}$。如果 $\text{ord}_n(a)=\varphi(n)$ 則稱 $a$ 為 $n$ 的原根
:::

我們默認大家都會原根的性質。如果不會的話，可以先相信以下性質，證明略。

:::danger
1. $\text{ord}_n(a)$ 整除 $\varphi(n)$。
2. 質數有原根。
3. 給定質數 $p$ 和原根 $g$，$\{g, g^2, g^3, \cdots, g^{p-1}\}$ 構成模 $p$ 下的既約剩餘系。
:::

接著我們注意到由餘式定理有 $f(x)$ 被 $x(x-1)$ 整除。我們觀察以下性質

:::danger
性質：$x^x$ 在模 $p$ 下每 $p(p-1)$ 個一循環。
證明：取一個 $p$ 的原根 $g$，注意到 $g, g+p, g+2p, g+3p, \cdots , g+p(p-2)$ 在模 $p-1$ 下兩兩不同餘。因此在模 $p$ 下有 $\{g, g^2, g^3, \cdots, g^{p-1}\}=\{g^g, g^{g+p}, g^{g+2p}, \cdots, g^{g+p(p-2)}\}$。因此 $x^x$ 的循環節大小並且循環節大小絕對超過 $p(p-2)$。又循環節大小必定是 $p$ 的倍數。因此其大小至少為 $p(p-1)$。而我們有 $(x+p(p-1))^{x+p(p-1)}\equiv x^{x+p(p-1)}\equiv x^x\times x^{p(p-1)}\equiv x^x\pmod{p}$。因此得證。
:::

因此若 $1$ 到 $p(p-1)$ 有 $A$ 個滿足條件的數，那答案就會是 $\frac{Af(p)}{p(p-1)}$。現在我們要計算這個 $A$ 的值。

:::danger
性質：$$A=\sum_{s=1}^{p-1}\gcd(s, p-1)$$
證明：考慮一個不被 $p$ 整除的正整數 $a$，以及一個原根 $g$，我們知道存在唯一一個小於 $p$ 的正整數 $k$ 使得 $g^k\equiv a\pmod{p}$。因此 $\{a^a, a^{a+p}, a^{a+2p}, \cdots, a^{a+p(p-2)}\}=\{a, a^2, a^3, \cdots, a^{p-1}\}=\{g^k, g^{2k}, g^{3k}, \cdots, g^{(p-1)k}\}$
而當 $p-1\mid tk$ 的時候 $g^{tk}\equiv 1\pmod{p}$。也就是說，當$(p-1)/\gcd(k, p-1)$ 整除 $t$ 的時候都會好，因此總共有 $\gcd(k, p-1)$ 個 $t$ 會好。對每個 $1\leq a\leq p-1$ 計算總和即可。
:::

這樣我們就可以 $O(p+n)$ 算出答案了。可是 $p$ 到六兆會噴爛欸，怎麼辦。我們定義 $gs(x)=\sum_{s=1}^x\gcd(s, x)$ 並觀察以下性質

::: danger
性質：
$$gs(x)=x\sum_{d|x}\frac{\varphi(d)}{d}$$
證明：
注意到滿足 $\gcd(s, x)=k$ 的數有 $\varphi(\frac{x}{k})$ 個，因此
$$gs(x)=\sum_{k|x}k\varphi(\frac{x}{k})=\sum_{d|x}\frac{\varphi(d)}{\frac{x}{d}}=x\sum_{d|x}\frac{\varphi(d)}{d}$$
:::

那這樣可以做什麼呢？我們希望它有積性，結果它就真的有了。

::: danger
性質：$gs(xy)=gs(x)gs(y)$
證明：
$$\begin{align*}gs(xy)&=xy\sum_{d|xy}\frac{\varphi(d)}{d}=xy\sum_{d|x, e|y}\frac{\varphi{(de)}}{de}\\&=\left(\sum_{d|x}\frac{\varphi(d)}{d}\right)\left(\sum_{e|y}\frac{\varphi(e)}{e}\right)=gs(x)gs(y)\end{align*}$$
:::

並且注意到 $gs(q^{\alpha})=(\alpha+1)q^{\alpha}-\alpha q^{\alpha-1}$ ($q$ 是質數)。。因此我們可以把 $p-1$ 質因數分解，對每個質因數計算 $gs$ 之後相乘。就可以算出 $A$。這樣總複雜度為 $O(\sqrt{p}+n)$，可以過。

預期難度：2900*
:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<ll, int>

ll mod=998244353;
const int MAXN=200005;
ll pw[MAXN],a[MAXN];
vector <pii> fac;

ll inv(ll x){
    if(x<=1) return x;
    return mod-mod/x*inv(mod%x)%mod;
}

void factorization(ll x){
    ll fs=2, mv=x;
    int temp;
    while(fs*fs<=mv){
        temp=0;
        while(mv%fs==0){
            mv/=fs;
            temp++;
        }
        if(temp>0) fac.pb({fs, temp});
        fs++;
    }
    if(mv>1) fac.pb({mv, 1});
}

ll gs(ll pr, ll alpha){
    ll temp=1, ans=0, prt=pr%mod;
    for(int i=1; i<=alpha-1; i++){
        temp*=prt;
        temp%=mod;
    }
    ans-=((alpha*temp)%mod);
    temp*=prt;
    temp%=mod;
    ans+=(((alpha+1)*temp)%mod);
    ans%=mod;
    return ans;
}

int main(){
    int n; ll p;
    cin>>n>>p;
    for(int i=0; i<=n; i++) cin>>a[i];
    ll pm=p%mod;
    pw[0]=1;
    for(int i=1; i<=n; i++){
        pw[i]=pw[i-1]*pm;
        pw[i]%=mod;
    }
    ll fp=0;
    for(int i=1; i<=n; i++){
        fp+=pw[i]*a[i];
        fp%=mod;
    }
    if(fp<0) fp+=mod;
    fp*=inv((pm*(pm-1))%mod);
    fp%=mod;
    factorization(p-1);
    for(pii pi: fac){
        fp*=gs(pi.first, pi.second);
        fp%=mod;
    }
    cout<<fp;
}

:::