a. Industrial questions / a

For operations with modulo, divide by a number and multiply by the inverse!!!!!!!!!!!!!!!!!!

The contribution of values in different positions to the final answer does not affect each other. The contribution of each value is considered separately

Considering that the contribution of the value located at \ ((x,y) \) to \ ((n,m) \), no matter which path you take, must be the original number \ (* a^{m-x}*b^{n-y} \), and the number of paths contributing to the answer is \ ((x,y) - > (n,m) \), which is obviously a combined number. L indicates how many steps you need to take, r indicates how many steps you need to take to the right (or down), so the number of schemes is \ (C_l^r \), We start with the unique number of schemes, so that each time we pass \ (C_l^r \), we only need \ (* (l+1)/(r+1) \) to find \ (C_{l+1}^{r+1} \) and remember to use the inverse element

#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. Card frequently asked questions / b

N points, 2n edges, or connected graph, then there is and only one ring in the graph, which is a base ring tree

If a y-point and its black-and-white edge are regarded as one edge, the y-point can be omitted and the black-and-white edge can be added to the x-point as the weight of the point. In this way, the base ring tree is still obtained

In fact, the problem can be transformed into that any two adjacent points on the base ring tree must have an activation, and the activation cost is the minimum cost of point weight

One of the two points connected by any edge must be activated. We consider breaking one side of the ring and transforming it into an ordinary tree DP. Two DP activates the two disconnected points respectively, and take a 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. Metaphysical questions / c

Examination room brain pumping series

It is found that it will have an effect only if it is a complete square number (odd factors),

To enumerate n, you only need to multiply the number of known \ (i(i\in[1,n])[1,m] \) by the complete square number

Write i in the form of \ (q*p_1^2 \), where q does not contain the square factor. The number multiplied by i as a complete square number can be written as \ (q*p_2^2 \)

The problem is transformed into finding the complete square number less than or equal to \ (m/q \). It is not difficult to think of how many square numbers can be obtained

\(sqrt(m/q) \) is the required value

#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;
}