A. 工业题 / a

带取模的运算，除以一个数一定要乘逆元！！！！！！！！！！！！！！！！！！

不同位置的值对最终答案的贡献是互不影响的，分开考虑每个值的贡献

考虑对于位于\((x,y)\)的值对\((n,m)\)的贡献，无论从哪个路径走过去，一定是原数\(*a^{m-x}*b^{n-y}\),而对答案贡献多少次即为\((x,y)->(n,m)\)不同的路径数,这个显然是个组合数，用l表示需要走几步，r表示需要向右（或下）走几步，那么方案数为\(C_l^r\)，为了方便计算，我们从方案数唯一的开始算，这样每次通过\(C_l^r\),求\(C_{l+1}^{r+1}\)只需要\(*(l+1)/(r+1)\)记得用逆元

#include<cstdio>
#include<cstring>
using namespace std;
const int mod=998244353;
long long a,b;
long long x[300005],y[300005];
int n,m;
long long qp(long long x,long long y){
    long long ans=1;
    while(y){
        if(y&1)ans=(ans*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return ans;
}
int main(){
    scanf("%d%d%lld%lld",&n,&m,&a,&b);
    for(int i=1;i<=n;++i)scanf("%lld",&x[i]);
    for(int i=1;i<=m;++i)scanf("%lld",&y[i]);
    for(int i=1;i<=n;++i)x[i]%=mod;
    for(int i=1;i<=m;++i)y[i]%=mod;
    a%=mod;b%=mod;
    long long nm=qp(a,m),nn=qp(b,n);
    long long c=1,l=m-1,r=0,ans=0,num=nm;
    for(int i=n;i>=1;--i){
        ans=(ans+((x[i]*c)%mod*num)%mod)%mod;
        ++l,++r;c=(c*(l%mod)%mod*qp(r,mod-2))%mod;num=(num*b)%mod;
    }
    c=1,l=n-1,r=0,num=nn;
    for(int i=m;i>=1;--i){
        ans=(ans+((y[i]*c)%mod*num)%mod)%mod;
        ++l,++r;c=((c*l)%mod*qp(r,mod-2))%mod;num=(num*a)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

B. 卡常题 / b

n个点，2n条边，还是连通图，那么图中有且只有一个环，是一棵基环树

如果将一个y点和其黑白边看成一条边，可以省去y点，将黑白边当作点权加到x点上，这样仍然得到基环树

其实问题已经可以转化为在基环树上任意相邻两点必须有一个激活，激活费用为点权的最小花费

任意一条边所连的两点必然有一个被激活，我们考虑断掉环上的一边，转化为普通的树形DP，两次DP分别激活断开的两点，取个min即可

#include<cstdio>
#include<cstring>
using namespace std;
int min(int x,int y){return x<y?x:y;}
const int maxn=1000005;
struct edge{
    int to,net;
}e[maxn<<1|1];
int d[maxn],head[maxn],tot=1;
void add(int u,int v){
    e[++tot].net=head[u];
    head[u]=tot;
    e[tot].to=v;
}
bool vis[maxn];
int del,root1,root2;
bool dfs(int x,int fx){
    vis[x]=1;
    for(int i=head[x];i;i=e[i].net){
        int v=e[i].to;
        if(v==fx)continue;
        if(vis[v]){del=i;root1=x;root2=v;return 1;}
        if(dfs(v,x))return 1;
    }
    return 0;
}
int f[maxn][2];
void work(int x,int fx){
    for(int i=head[x];i;i=e[i].net){
        int v=e[i].to;
        if(v==fx||i==del||i==(del^1))continue;
        work(v,x);
        f[x][0]+=f[v][1];
        f[x][1]+=min(f[v][0],f[v][1]);
    }
    f[x][1]+=d[x];
}
int n;
int main(){
    int a,b;
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;++i){
        int u,v;scanf("%d%d",&u,&v);
        d[u]+=a;d[v]+=b;add(u,v);add(v,u);
    }
    bool p=dfs(1,0);
    work(root1,0);
    int ans=f[root1][1];
    memset(f,0,sizeof(f));
    work(root2,0);
    ans=min(ans,f[root2][1]);
    printf("%d\n",ans);
    return 0;
}

C. 玄学题 / c

考场脑抽系列

发现是完全平方数才会有影响（奇数个因子），

枚举n只需求对已知\(i(i\in[1,n])[1,m]\)中有多少数与之相乘为完全平方数

将i写成\(q*p_1^2\)的形式，其中q不含平方因子，与i相乘为完全平方数的数一定能写成\(q*p_2^2\)

问题转化为求小于等于\(m/q\)的完全平方数有几个，开方即可，不难想到

\(sqrt(m/q)\)即为所求

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=10000005;
long long a[maxn];
long long n,m;
void work(){
    for(long long i=1;i*i<=n;++i)
     for(long long j=1;j*i*i<=n;++j)
       a[i*i*j]=j;
    long long ans=0;
    for(long long i=1;i<=n;++i)
     if(((long long)sqrt(m/a[i]))&1)--ans;
     else ++ans;
    printf("%lld\n",ans);
}
int main(){
    scanf("%lld%lld",&n,&m);
    work();
    return 0;
}