9.8度小满笔试 AK

选择题又是C++又是java又是php是什么鬼，第2，3题基本是同一类型的，有点重复了。

1、

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

int main()
{
    int n,k;
    string s;
    cin>>n>>k>>s;
    int cnt=0;
    for(int i=0;i<n;i++)
        if(s[i]=='A')
            cnt++;
    long long ans,r;
    if(k%cnt==0)
    {
        ans=(long long)(k/cnt-1)*n;
        r=cnt;
    }
    else
    {
        ans=(long long)k/cnt*n;
        r=k%cnt;
    }
    cnt=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='A')
            cnt++;
        if(cnt==r)
        {
            ans+=i+1;
            break;
        }
    }
    cout<<ans;
}

2、

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

const int N=50005,mod=1e9+7;

vector<int> g[N];
long long n,c[N],ans[N];

void dfs(int u,int f)
{
    // cout<<u<<endl;
    if(g[u].size()==1)
    {
        ans[u]=1;
        return;
    }
    vector<int> s;
    for(int v:g[u])
    {
        if(v!=f)
        {
            dfs(v,u);
            s.push_back(v);
        }
    }
        
    if(c[u]==1)
        ans[u]=(ans[s[0]]+ans[s[1]])%mod;
    else
        ans[u]=(ans[s[0]]*ans[s[1]])%mod;
}
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        int p;
        cin>>p;
        g[p].push_back(i);
        g[i].push_back(p);
    }
    for(int i=1;i<=n;i++)
        cin>>c[i];
    dfs(1,0);
    cout<<ans[1];
}

3、居然是树哈希，金牌题！

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

int n,A,B,M;
vector<int> g[10005];
long long h[10005];

long long qmi(int a,int b)
{
    long long ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%M;
        a=a*a%M;
        b>>=1;
    }
    return ans;
}
void dfs(int u,int f)
{
    for(int v:g[u])
    {
        if(v!=f)
        {
            dfs(v,u);
            h[u]=(h[u]+(h[v]+qmi(A,u))%M*B%M)%M;
        }
    }
}
signed main()
{
    cin>>n>>A>>B>>M;
    for(int i=2;i<=n;i++)
    {
        int p;
        cin>>p;
        g[i].push_back(p);
        g[p].push_back(i);
    }
    dfs(1,0);
    cout<<h[1];
}