题面：https://www.cnblogs.com/Juve/articles/11484209.html
工业：
推一个式子，AC
没有用组合数。。。。推了2个多小时
我sbsbsbsbsbsbsbsbsbsbsbsbsbsbsb
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int MAXN=3e5+5;
const int mod=998244353;
int n,m,a,b,inn[MAXN],inm[MAXN],fm[MAXN],fn[MAXN],ans=0;
int q_pow(int a,int b,int p){
int res=1;
while(b){
if(b&1) res=res%p*a%p;
a=a%p*a%p;
b>>=1;
}
return res%p;
}
signed main(){
//freopen("a_sample2.in","r",stdin);
//freopen("vio.out","w",stdout);
scanf("%lld%lld%lld%lld",&n,&m,&a,&b);
a%=mod,b%=mod;
for(int i=1;i<=n;++i) scanf("%lld",&inn[i]),inn[i]%=mod;
for(int i=1;i<=m;++i) scanf("%lld",&inm[i]),inm[i]%=mod;
fm[1]=1;
for(int i=2;i<=m;++i){
fm[i]=fm[i-1]*(n-2+i)%mod*q_pow(i-1,mod-2,mod)%mod;
//cout<<fm[i]<<endl;
}
fn[1]=1;
for(int i=2;i<=n;++i){
fn[i]=fn[i-1]*(m-2+i)%mod*q_pow(i-1,mod-2,mod)%mod;
//cout<<fn[i]<<endl;
}
for(int i=1;i<=n;++i){
//cout<<i<<' '<<0<<' '<<fn[n-i+1]<<' '<<m<<' '<<n-i<<endl;
(ans+=inn[i]%mod*fn[n-i+1]%mod*q_pow(a,m,mod)%mod*q_pow(b,n-i,mod)%mod)%=mod;
}
for(int i=1;i<=m;++i){
//cout<<0<<' '<<i<<' '<<fm[m-i+1]<<' '<<m-i<<' '<<n<<endl;
(ans+=inm[i]%mod*fm[m-i+1]%mod*q_pow(a,m-i,mod)%mod*q_pow(b,n,mod)%mod)%=mod;
}
printf("%lld
",ans%mod);
return 0;
}
卡常：
基环树dp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
const int MAXN=1e6+5;
int n,a,b,ans=0x7fffffff;
int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],val[MAXN],cnt=1;
inline void add(re int u,re int v){
cnt++,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;
}
bool vis[MAXN];
int st,ed,edge,f[MAXN],g[MAXN];
inline void dfs(re int x,re int fa,re int id){
if(vis[x]){
edge=id;
st=fa,ed=x;
return ;
}
vis[x]=1;
for(re int i=pre[x];i;i=nxt[i]){
re int y=to[i];
if(y==fa) continue;
dfs(y,x,i);
}
}
inline void DFS(re int x,re int fa){
g[x]=0,f[x]=val[x];
for(re int i=pre[x];i;i=nxt[i]){
re int y=to[i];
if(y==fa) continue;
if(edge==i||edge==(i^1)) continue;
DFS(y,x);
f[x]+=min(g[y],f[y]);
g[x]+=f[y];
}
}
signed main(){
scanf("%d%d%d",&n,&a,&b);
for(re int i=1;i<=n;++i){
re int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
val[x]+=a,val[y]+=b;
}
dfs(1,0,0);
DFS(st,0);
ans=min(f[st],ans);
DFS(ed,0);
ans=min(f[ed],ans);
printf("%d
",ans);
return 0;
}
玄学：
那个-1的幂是由d(i*j)的和的奇偶性决定的。
d(x)为偶数时并没有任何影响,我们只考虑d(x)为奇数的时候,
不难想到,x这个时候是完全平方数。
我们把i拆成$p*q^2$(p没有平方因子),那j必须有$p*r^2$的形式,
所以对于每个i,都有$sqrt{frac{m}{p}}$个j产生贡献。
至于p的求法,线性筛即可。
我们知道，质数的p就是它本身
然后筛就好了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=1e7+2;
long long n,m,ans=0;
int prime[MAXN],vis[MAXN],p[MAXN],tot;
void get_p(long long n){
vis[1]=p[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]) prime[++tot]=i,p[i]=i;
for(int j=1;j<=tot&&i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(!(p[i]%prime[j])){
p[i*prime[j]]=p[i]/prime[j];
break;
}
else p[i*prime[j]]=p[i]*p[prime[j]];
}
}
}
signed main(){
scanf("%lld%lld",&n,&m);
get_p(n);
for(int i=1;i<=n;++i){
int sum=sqrt(m/p[i]);
if(sum%2) --ans;
else ++ans;
}
printf("%lld
",ans);
return 0;
}