12.10 模拟赛

T1 bishop

题目大意：

n个点组成了一些环 在这n个点中等概率选k个点（不能重复） 染了一个点就会染该环上的所有点

求所有点都被染色的概率

思路：

可以设$F_{i,j}$  表示在$i$个环放$k$个点的方案数即$F_{i,j}=C(i,j)$，$if space j==0 ：F_{i,j}=0$

我们考虑生成函数即合并两个数组 发现是卷积 所以我们直接建出初始数组 然后分治一样两两卷积

就过了

 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 170100
17 #define MOD 998244353
18 using namespace std;
19 inline int read()
20 {
21     int x=0,f=1;char ch=getchar();
22     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
23     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
24     return x*f;
25 }
26 int N,n,m,k,vis[MAXN],to[MAXN],sz[MAXN],tot;
27 int fac[MAXN],inv[MAXN],rev[MAXN<<2],inv3;
28 ll A[MAXN<<2],B[MAXN<<2],lmt,lg;
29 vector <int> vec[MAXN];
30 void dfs(int x) {sz[tot]++,vis[x]=1;if(!vis[to[x]]) dfs(to[x]);}
31 ll q_pow(ll bas,ll t,ll res=1)
32 {
33     for(;t;t>>=1,(bas*=bas)%=MOD)
34         if(t&1) (res*=bas)%=MOD;return res;
35 }
36 int C(int n,int m) {return ((ll)((((ll)fac[n]*inv[m])%MOD)*inv[n-m]))%MOD;}
37 void ntt(ll *a,int n,int f)
38 {
39     rep(i,0,n-1) if(i<rev[i])swap(a[i],a[rev[i]]);
40     for(int i=1;i<n;i<<=1)
41     {
42         ll wn=q_pow(3,(MOD-1)/(i<<1))%MOD;
43         if(f==-1)wn=q_pow(wn,MOD-2);
44         for(int j=0;j<n;j+=i<<1)
45         {
46             ll w=1,x,y;
47             for(int k=0;k<i;k++,w=wn*w%MOD)
48                 x=a[k+j],y=((ll)a[k+j+i]*w)%MOD,a[j+k]=(x+y)%MOD,a[j+k+i]=(x-y+MOD)%MOD;
49         }
50     }
51     if(f==1) return ;int nv=q_pow(n,MOD-2);
52     for(int i=0;i<n;i++) a[i]=a[i]*nv%MOD;
53 }
54 void Div(int l,int r,ll tmp)
55 {
56     if(l==r) return ;int mid=(l+r)>>1;
57     int t1=min(sz[mid]-sz[l-1],k-1),t2=min(sz[r]-sz[mid],k-1);
58     Div(l,mid,t1);Div(mid+1,r,t2);tmp=t1+t2;lmt=1,lg=0;
59     while(lmt<=tmp) lmt<<=1,lg++;
60     for(int i=0;i<lmt;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
61     rep(i,0,t1) A[i]=vec[l][i];rep(i,t1+1,lmt-1) A[i]=0;
62     rep(i,0,t2) B[i]=vec[mid+1][i];rep(i,t2+1,lmt-1) B[i]=0;/*
63     rep(i,0,lmt-1) cout<<A[i]<<" ";cout<<endl;
64     rep(i,0,lmt-1) cout<<B[i]<<" ";cout<<endl;*/
65     ntt(A,lmt,1);ntt(B,lmt,1);
66     rep(i,0,lmt) (A[i]*=B[i])%=MOD;
67     ntt(A,lmt,-1);vec[l].clear();vec[mid+1].clear();
68     rep(i,0,min(tmp,(ll)k)) vec[l].push_back(A[i]);
69 }
70 int main()
71 {
72     freopen("bishop.in","r",stdin);
73     freopen("bishop.out","w",stdout);
74     int T=read(),x;inv[0]=inv[1]=fac[0]=1;
75     rep(i,2,152501) inv[i]=((ll)(MOD-MOD/i)*inv[MOD%i])%MOD;inv3=inv[3];
76     rep(i,1,152501) fac[i]=((ll)fac[i-1]*i)%MOD,inv[i]=((ll)inv[i-1]*inv[i])%MOD;
77     while(T--)
78     {
79         Fill(vis,0);Fill(sz,0);
80         n=read(),k=read()+1,tot=0;rep(i,1,n) to[i]=read();
81         rep(i,1,n) if(!vis[i]) tot++,dfs(i);
82         x=n,n=tot;rep(i,1,n) {vec[i].push_back(0);rep(j,1,min(sz[i],k-1)) vec[i].push_back(C(sz[i],j));}
83         //rep(i,1,n) {for(auto x:vec[i]) cout<<x<<" ";puts("");}
84         rep(i,1,n) sz[i]+=sz[i-1];//cout<<sz[1]<<" "<<sz[2]<<endl;
85         Div(1,n,k);printf("%lld
",((ll)(vec[1][k-1]*q_pow(C(x,k-1),MOD-2)))%MOD);
86         rep(i,1,n) vec[i].clear();
87     }
88     fclose(stdout);return 0;
89 }
View Code

T2 decoration

题目大意：

一个$N$行，$M$列的矩形 设$F_{N,M}$求用$1 imes 2$和$2 imes 1$ 有多少种方案能铺满整个矩形

给出$L R$ 求$F_{L,M} + F_{L+1,M}+F_{L+2,M} ··· F_{R,M}$

思路：

正解是特征多项式 当然是不会啊

由于dp只与前一行有关，通过状压搜出转移矩阵

然后用优秀的十进制快速幂 在矩阵里加一维记录前缀和

 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(register 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 MOD 998244353
17 #define MAXN 2001000
18 using namespace std;
19 inline int read()
20 {
21     int x=0,f=1;char ch=getchar();
22     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
23     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
24     return x*f;
25 }
26 char chl[2520],chr[2520];
27 int tot,ans,m,s1,s2,g[260],vis[260];
28 struct Mat
29 {
30     int num[260][260];
31     Mat() {memset(num,0,sizeof(num));}
32     Mat operator * (const Mat &a) const
33     {
34         Mat res;
35         rep(i,0,tot) rep(j,0,tot) rep(k,0,tot) (res.num[i][j]+=((ll)num[i][k]*a.num[k][j])%MOD)%=MOD;
36         return res;
37     }
38     void print() {rep(i,0,tot) {rep(j,0,tot) cout<<num[i][j]<<" ";cout<<endl;}cout<<endl;}
39 }st,tmp;
40 int q_pow(int bas,int t,int res=1)
41 {
42     for(;t;t>>=1,bas=(ll)bas*bas%MOD)
43         if(t&1) res=(ll)res*bas%MOD;
44     return res;
45 }
46 void dfs(int x,int i,int stat,int c1,int c2)
47 {
48     if(i==m)
49     {
50         if(vis[stat]==-1) vis[stat]=tot,g[tot++]=stat;
51         (st.num[x][vis[stat]]+=((ll)q_pow(s1,c1)*q_pow(s2,c2)%MOD))%=MOD;
52     }
53     else if(g[x]&(1<<i)) dfs(x,i+1,stat,c1+1,c2);
54     else
55     {
56         if(i+1<m&&(g[x]&(1<<i+1))==0) dfs(x,i+2,stat,c1,c2+1);
57         dfs(x,i+1,stat|(1<<i),c1,c2);
58     }
59 }
60 int work(char *s)
61 {
62     Mat res,two;rep(i,0,tot) res.num[i][i]=1;
63     int len=strlen(s),val;dwn(i,len-1,0)
64     {
65         val=s[i]-'0';if(val&1) res=tmp*res;
66         tmp=tmp*tmp,two=tmp;if(val&2) res=tmp*res;
67         tmp=tmp*tmp;if(val&4) res=tmp*res;
68         tmp=tmp*tmp;if(val&8) res=tmp*res;
69         tmp=tmp*two;
70     }
71     return (res.num[0][tot]+res.num[tot][0])%MOD;
72 }
73 int main()
74 {
75     freopen("decoration.in","r",stdin);
76     freopen("decoration.out","w",stdout);
77     scanf("%s%s",chl,chr);m=read(),s1=read(),s2=read();int len=strlen(chl);
78     dwn(i,len-1,0) if(chl[i]=='0') chl[i]='9';else {chl[i]--;break;}
79     Fill(vis,0xff);vis[0]=0,g[tot++]=0;rep(i,0,tot-1) dfs(i,0,0,0,0);
80     rep(i,0,tot-1) st.num[i][tot]=st.num[i][0];st.num[tot][tot]=1;
81     tmp=st;ans=-work(chl);tmp=st;(ans+=work(chr)+MOD)%=MOD;
82     printf("%d
",ans);
83 }
View Code

T3 conference

题目大意：

一颗树 每个点有人数和边权 支持两个操作

1. 修改单点的人数

2.在$x-y$链上找一个点使得其他点的人走到这个点的距离和最小 输出这个距离

思路：

对于询问 要求的点为带权中位数 所以可以在ST表上二分来找到这个点

用两个树状数组分别维护每个点到根的人数和以及（该点人数*该点到根路径长度）到根的和

计算答案的时候加加减减即可

 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(register 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 MOD 998244353
17 #define MAXN 170100
18 using namespace std;
19 inline int read()
20 {
21     int x=0,f=1;char ch=getchar();
22     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
23     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
24     return x*f;
25 }
26 int n,m,v[MAXN],fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],val[MAXN<<1],f[MAXN][20];
27 int dep[MAXN],in[MAXN],ou[MAXN],tot,cnt;
28 ll dis[MAXN],tmp;
29 void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}
30 void dfs(int x,int pa)
31 {
32     for(int i=1;(1<<i)<=dep[x];i++) f[x][i]=f[f[x][i-1]][i-1];in[x]=++tot;
33     ren if(to[i]!=pa)
34         dep[to[i]]=dep[x]+1,dis[to[i]]=dis[x]+val[i],f[to[i]][0]=x,dfs(to[i],x);
35     ou[x]=tot;
36 }
37 inline int lca(int u,int v)
38 {
39     if(dep[u]<dep[v]) swap(u,v);int t=dep[u]-dep[v];
40     dwn(i,19,0) if((1<<i)&t) u=f[u][i];if(u==v) return u;
41     dwn(i,19,0) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
42     return f[u][0];
43 }
44 struct Fenwick
45 {
46     ll c[MAXN];
47     inline int lowbit(int x) {return x&(-x);}
48     inline void mdf(int x,ll val) {for(;x<=n;x+=lowbit(x)) c[x]+=val;}
49     inline ll query(int x) {if(x<=0) return 0LL;ll res=0;for(;x;x-=lowbit(x)) res+=c[x];return res;}
50 }c1,c2;
51 void mdfc(int x,int t)
52 {
53     c1.mdf(in[x],t);c1.mdf(ou[x]+1,-t);
54     c2.mdf(in[x],t*dis[x]);c2.mdf(ou[x]+1,-t*dis[x]);v[x]+=t;
55 }
56 ll cheque(int x,int z,int i)
57 {
58     int t1=dep[x]-dep[z];
59     if((1<<i)<=t1) return tmp=c1.query(in[x])-c1.query(in[f[x][i]]);
60     else return tmp=1LL<<60;
61 }
62 ll calc(int x,int anc){return c2.query(in[x])-c2.query(in[anc])-dis[anc]*(c1.query(in[x])-c1.query(in[anc]));}
63 ll work(int x,int y)
64 {
65     int z=lca(x,y),sum=c1.query(in[x])+c1.query(in[y])-(c1.query(in[z])<<1)+v[z],res=0,pos;sum=ceil(sum/2.0);
66     if(v[x]>=sum) res=pos=x,res=1;
67     else if(v[y]>=sum) res=pos=y,res=0;
68     else if(c1.query(in[x])-c1.query(in[z])>=sum){pos=x;dwn(i,19,0) if(res+cheque(x,z,i)<sum) x=f[x][i],res+=tmp;res=1;}
69     else {pos=y;dwn(i,19,0) if(res+cheque(y,z,i)<sum) y=f[y][i],res+=tmp;res=0;}
70     if(res) res=x,x=pos;else res=y,y=pos,swap(x,y);ll ans=0;
71     ans=calc(y,z)+(dis[res]-dis[z])*(c1.query(in[y])-c1.query(in[z]))+calc(x,res);
72     ans+=(dis[res]-dis[z])*(c1.query(in[res])-c1.query(in[z])+v[z])-calc(res,z);
73     return ans;
74 }
75 int main()
76 {
77     freopen("conference.in","r",stdin);
78     freopen("conference.out","w",stdout);
79     n=read();int a,b,c;rep(i,1,n) v[i]=read();
80     rep(i,2,n) a=read(),b=read(),c=read(),add(a,b,c),add(b,a,c);
81     dfs(1,0);rep(i,1,n) mdfc(i,v[i]),v[i]>>=1;m=read();
82     while(m--)
83     {
84         c=read(),a=read(),b=read();
85         if(c==1) printf("%lld
",work(a,b));else mdfc(a,b-v[a]);
86     }
87 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yyc-jack-0920/p/10109735.html