12.3 模拟赛

过于神仙的比赛

T1 graph

题目大意：

一个无向图若其的一个子图存在欧拉回路则答案+=这个子图边数的平方

思路：

对于一个连通图发现一个奇妙的结论即这个联通块的方案数＝$2^{m-n+1}$（n为点数，m为边数

然后对于多个联通块方案数为$2^{m-n+c}$，c为联通块数量

而答案可以转化为$sum_{x=1}^{m} sum_{y=1}^{m} F(x,y)$

其中$ F(x,y)$表示强制选x和y这两条边的答案可以发现若有桥边则一定无解

所以现在考虑选了两条边后对答案的影响若联通块数+1 则对答案的贡献为$2^{m-n-1}$ 否则为$2^{m-n-2}$

则这道题变成了在无向图上选两条边对联通块数量的影响可以参考bzoj 3569

对每个非树边rand一个权值一个树边的权值为覆盖这条边的所有权值异或和若两条边异或和为0 则说明选这两条边会使联通块数量+1

最后统计一下答案

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<vector>
 8 #include<stack>
 9 #include<queue>
10 #include<map>
11 #define rep(i,s,t) for(register int i=(s),i__end=(t);i<=i__end;++i)
12 #define dwn(i,s,t) for(register int i=(s),i__end=(t);i>=i__end;--i)
13 #define ren for(int i=fst[x];i;i=nxt[i])
14 #define Fill(x,t) memset(x,t,sizeof(x))
15 #define ll long long
16 #define ull unsigned long long
17 #define inf 2139062143
18 #define MAXN 170100
19 #define MOD 998244353
20 using namespace std;
21 inline int read()
22 {
23     int x=0,f=1;char ch=getchar();
24     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
25     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
26     return x*f;
27 }
28 int n,m,N,fst[MAXN],to[MAXN<<1],nxt[MAXN<<1],cnt=1,vis[MAXN][2],dfn;//num为所有非桥边，tot为所有使联通块数量+1的边对 
29 ull val[MAXN],v[MAXN<<1],ans=1,tot,num;
30 map <ull,int> hsh;//记录所有边权相同的边
31 void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
32 inline ull rnd(){ull res=(rand()^(rand()<<16));res<<=32,res|=(rand()^(rand()<<16));return res;}//优秀的ULL rand 
33 void dfs(int x,int pa)
34 {
35     vis[x][0]=++dfn;ren if(i!=(pa^1))
36     {
37         if(!vis[to[i]][0]) dfs(to[i],i);
38         else if(vis[to[i]][0]<vis[x][0])//处理非树边的权值并对这个路径的两端异或该值，在下一次dfs时候可以保证所有路径上的边都被异或（脑补一下 
39             tot++,num++,v[i]=rnd(),val[x]^=v[i],val[to[i]]^=v[i],hsh[v[i]]++;
40     }
41 }
42 void Dfs(int x,int pa)
43 {
44     vis[x][1]=1;ren if(i!=(pa^1)&&!vis[to[i]][1]) {Dfs(to[i],i);val[x]^=val[to[i]];}
45     if(val[x]) {num++;(tot+=(hsh[val[x]]<<1|1))%=MOD;hsh[val[x]]++;}//计算所有边权相同的边对 
46 }
47 int main()
48 {
49     freopen("graph.in","r",stdin);
50     freopen("graph.out","w",stdout);
51     srand(19260817);ll res2;
52     n=read(),m=read(),N=m-n-2,res2=1;int a,b;rep(i,1,m) a=read(),b=read(),add(a,b),add(b,a);
53     rep(i,1,n) if(!vis[i][0]) {dfs(i,-1);Dfs(i,-1);N++;}
54     rep(i,1,N) (ans<<=1)%=MOD;//不影响联通块数量的每个边对的答案
55     rep(i,1,N+1) (res2<<=1)%=MOD;
56     ((num*=num)-=tot)%=MOD;
57     ans=((tot*res2)%MOD+ans*num)%MOD;
58     printf("%lld
",ans);
59 }

View Code

（代码中的res2不能用$ans<<1$代替，因为N+1可能小于1

T2 math

题目大意：

思路：

首先可以构造一个狄利克雷卷积 $G=F*mu$

当$d=1$的时候 $G(p)=0$ 发现$G(p^c)=F(p^c)-F(p^{c-1})$

由于$G(i)$为积性函数所以$G(i)=G({p_1}^{c_1}) imes ··· G({p_k}^{c^k})$

则①$G(x)>0$的充要条件为x的每一个质因子的次数都$geq 2$

这样可以使有意义的$G$数量变少又可以把$G$卷回去即$F=G*1$

则$F(i)=sum_{d|n} G(d)$ 然后答案为$sum_{i=1}^n G(i) imes lfloor frac{n}{i} floor$

由①得对于所有对答案有贡献的$G(i)，i$都可以表示为$a^2 imes b^3$的形式，

而这种数的数量为$n^{frac{1}{2}}$级别的可以搜索（使用每个质因子次数都$ge$2的性质）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<vector>
 8 #include<queue>
 9 #include<map>
10 #define rep(i,s,t) for(register int i=(s);i<=(t);++i)
11 #define dwn(i,s,t) for(register int i=(s);i>=(t);--i)
12 #define ren for(int i=fst[x];i;i=nxt[i])
13 #define Fill(x,t) memset(x,t,sizeof(x))
14 #define ll long long
15 #define inf 2139062143
16 #define MAXN 10010000
17 using namespace std;
18 inline ll read()
19 {
20     ll x=0,f=1;char ch=getchar();
21     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
22     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
23     return x*f;
24 }
25 int p[MAXN/10],tot,ntp[MAXN];
26 ll n,ans;
27 void mem(ll m)
28 {
29     rep(i,2,m)
30     {
31         if(!ntp[i]) p[++tot]=i,ntp[i]=1;
32         for(int j=1;i*p[j]<=m;j++) {ntp[i*p[j]]=1;if(i%p[j]==0) break;}
33     }
34 }
35 void dfs(int x,ll now,ll rst)
36 {
37     ans+=now*rst;ll tmp,t1,t2,res;
38     rep(i,x+1,tot)
39     {
40         tmp=rst;if((ll)p[i]*p[i]>rst) break;
41         tmp/=(ll)p[i]*p[i],t1=p[i],t2=1LL;
42         rep(j,2,60)
43         {
44             if(!tmp) break;
45             res=t1*(j%p[i]==0?p[i]:1)-t2*((j-1)%p[i]==0?p[i]:1);
46             dfs(i,now*res,tmp);tmp/=p[i],t1*=p[i],t2*=p[i];
47         }
48     }
49 }
50 int main()
51 {
52     freopen("sum.in","r",stdin);
53     freopen("sum.out","w",stdout);
54     n=read();mem(10000000);dfs(0,1LL,n);printf("%lld
",ans);
55     fclose(stdout);return 0;
56 }

View Code

T3 math

思路：

通过观察可以发现$T(i,j)=C(i,j)*(i+1)$ 然后经过一些观察发现所求其实为$lcm(n-k+1,n-k+2··· n)$

可以构造一个数列$A_i[]$ 使得 $prod_{i=l}^r A_r[i]=lcm(l,···,r)$

考虑已经构造好了$i-1$项现在要加入第$i$这个数则我们可以构造一个栈，分解$i$，在前面的数中将每个质数扔掉 eg：

* 6: 1 1 1 2 5 6

* 7: 1 1 1 2 5 6 7

* 8: 1 1 1 1 5 3 7 8

······

这样的话是需要将这一段的点乘起来即可由于强制在线使用主席树维护这个数组即可

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define rep(i,s,t) for(register int i=(s),i__end=(t);i<=i__end;++i)
#define dwn(i,s,t) for(register int i=(s),i__end=(t);i>=i__end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define Fill(x,t) memset(x,t,sizeof(x))
#define ll long long
#define inf 2139062143
#define MAXN 170100
#define MOD 998244353
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int tot,q,n,k,A,B,las,mod,c[MAXN],d[MAXN],inv[MAXN];
int vis[MAXN],pw[MAXN];
int ls[MAXN<<7],rs[MAXN<<7],rt[MAXN],val[MAXN<<7];
struct data {int id,val;};
vector <data> num[MAXN];
stack <data> st[MAXN];
void mdf(int &k,int kk,int l,int r,int x,int w)
{
    if(!k) k=++tot;val[k]=((ll)val[kk]*w)%MOD;
    if(l==r) return ;
    ls[k]=ls[kk],rs[k]=rs[kk];int mid=l+r>>1;
    if(x<=mid) {ls[k]=0;mdf(ls[k],ls[kk],l,mid,x,w);}
    else {rs[k]=0;mdf(rs[k],rs[kk],mid+1,r,x,w);}
}
int query(int k,int l,int r,int a,int b)
{
    if(l==a&&r==b) return val[k];
    int mid=l+r>>1;
    if(b<=mid) return query(ls[k],l,mid,a,b);
    else if(a>mid) return query(rs[k],mid+1,r,a,b);
    else return ((ll)query(ls[k],l,mid,a,mid)*query(rs[k],mid+1,r,mid+1,b))%MOD;
}
int main()
{
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
    q=read(),n=read(),k=read(),A=read(),B=read(),mod=read();swap(n,mod);
    inv[1]=val[0]=pw[0]=1;rep(i,2,n) inv[i]=((ll)(MOD-MOD/i)*inv[MOD%i])%MOD;
    rep(i,2,n) if(!vis[i])
    {
        rep(j,1,n) if(pw[j-1]<=n) pw[j]=pw[j-1]*i;else break;
        rep(j,i,n) {rep(o,1,n) if(j%pw[o]) {num[j].push_back((data){i,o-1});break;}vis[j]=1,j+=i-1;}
    }int x,y,p,t;
    rep(i,1,n)
    {
        mdf(rt[i],rt[i-1],1,n,i,i);
        rep(j,0,num[i].size()-1)
        {
            x=num[i][j].id,y=num[i][j].val;
            rep(o,1,n) if(pw[o-1]<=n) pw[o]=pw[o-1]*x;else break;
            while(st[x].size())
            {
                p=st[x].top().id,t=st[x].top().val;st[x].pop();
                if(y>=t) mdf(rt[i]=0,rt[i],1,n,p,inv[pw[t]]);
                else {mdf(rt[i]=0,rt[i],1,n,p,inv[pw[y]]);st[x].push((data){p,t-y});}
                y-=t;if(y<=0) break;
            }
            st[x].push((data){i,num[i][j].val});
        }
    }
    rep(i,1,q-1) c[i]=read();rep(i,1,q-1) d[i]=read();swap(n,mod);
    rep(i,1,q) {printf("%d
",las=query(rt[n],1,mod,n-k+1,n));n=((ll)A*las+c[i])%mod+1,k=((ll)B*las+d[i])%n+1;}
}

View Code