NOIP提高组模拟赛7

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
#include
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
#include
using namespace std;
int min(int x,int y){return x

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