2019.9.22
summary
- 回到了上半年的做题状态 知道难了 还在瓜想正解
- 该拿的分未拿到
- 日常瓜想
- 计算空间出错
==欧阳说各种情况都要经历一下 心态炸麻木了就好了
足球比赛
https://i.loli.net/2019/09/22/JKP8ufGywEjphBe.jpg
https://i.loli.net/2019/09/22/jvQPI7EoaY12sxO.jpg
脑壳痛
\(ans=\sum C_n^i((pa*(1-qb))^i*(pb*qb)^{n*P-2}\)
还卡卡空间== 所以就预处理出fac阶乘的逆
#include<bits/stdc++.h>
#define ll long long
#define rg register
const int N=1e7+5,M=100+5,P=1e9+7,INF=1e9+7,inf=0x3f3f3f3f;
int n,p,q,pa,pb,qa,qb,facn,sum=0,ans=0,ifac[N];
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
int qpow(int a,int b){
int ret=1;
while(b){
if(b&1) ret=(ll)ret*a%P;
a=(ll)a*a%P,b>>=1;
}
return ret;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("T1.txt","r",stdin);
//freopen("attack.out","w",stdout);
#endif
rd(n),rd(pa),rd(pb),rd(qa),rd(qb);
if(!pa||qa==qb) return puts("0"),0;
p=(ll)pa*qpow(pb,P-2)%P,q=(ll)qa*qpow(qb,P-2)%P;
facn=1;
for(rg int i=2;i<=n;++i) facn=(ll)facn*i%P;
ifac[n]=qpow(facn,P-2);
for(rg int i=n;i;--i) ifac[i-1]=(ll)ifac[i]*i%P;//i!的逆
int nwp=qpow((P+1-p)%P,n),nwq=qpow((P+1-q)%P,n);
int inv1=(ll)p*qpow((P+1-p)%P,P-2)%P;
int inv2=(ll)q*qpow((P+1-q)%P,P-2)%P;
for(int i=0;i<=(n>>1);++i)
ifac[n-i]=(ll)ifac[i]*ifac[n-i]%P,ifac[i]=ifac[n-i];
for(int i=1;i<=n;++i){
sum=(sum+(ll)nwq*ifac[i-1])%P,nwp=(ll)nwp*inv1%P;
ans=(ans+(ll)nwp*sum%P*ifac[i])%P,nwq=(ll)nwq*inv2%P;
}
ans=(ll)ans*facn%P;
if(p==1) ans=sum;
ans=(ll)ans*facn%P;
printf("%d\n",ans);
return 0;
}文明
其实很简单 考场上想出来了找两个点的中点来跳 可是并没有想到树剖然后线段树来维护其和
考场上打的暴力换根 再加上暴力上跳 结果没有想到跳到中点来 然后导致减重复了 其间还有很多低级错误\(QAQ\)
看到题解那个上跳到中点的操作之后就知道该怎么做了 一下子就打出来了
#include<bits/stdc++.h>
#define ll long long
#define ls (o<<1)
#define rs (o<<1|1)
using namespace std;
const int N=500000+5,M=100+5,P=7,INF=1e9+7,inf=0x3f3f3f3f;
int n,m,ans;
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
int head[N],tot=0;
struct edge{int v,nxt;}e[N<<1];
void add(int u,int v){e[++tot]=(edge){v,head[u]},head[u]=tot;}
int idx=0,dfn[N],id[N],son[N],f[N],dep[N],sz[N],top[N];
void dfs1(int u,int fa){
dep[u]=dep[fa]+1,f[u]=fa,sz[u]=1;
for(int i=head[u],v,mxs=-1;i;i=e[i].nxt)
if((v=e[i].v)!=fa){
dfs1(v,u),sz[u]+=sz[v];
if(mxs<sz[v]) mxs=sz[v],son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf,dfn[u]=++idx,id[idx]=u;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=head[u],v;i;i=e[i].nxt)
if((v=e[i].v)!=f[u]&&v!=son[u]) dfs2(v,v);
}
struct node{int sum,tg;}t[N<<2];
void pup(int o){t[o].sum=t[ls].sum+t[rs].sum;}
void updnode(int o,int l,int r,int k){t[o].sum=(r-l+1)*k,t[o].tg=k;}
void pudw(int o,int l,int r){
if(t[o].tg==-1) return;
int mid=l+r>>1;
updnode(ls,l,mid,t[o].tg),updnode(rs,mid+1,r,t[o].tg);
t[o].tg=-1;
}
void mdf(int o,int l,int r,int x,int y,int k){
if(l>y||r<x) return;
if(x<=l&&r<=y){updnode(o,l,r,k);return;}
pudw(o,l,r);
int mid=l+r>>1;
mdf(ls,l,mid,x,y,k),mdf(rs,mid+1,r,x,y,k);
pup(o);
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=f[top[x]];
}
return dep[x]<dep[y]?x:y;
}
int jump(int x,int k){
while(dep[x]-dep[top[x]]+1<=k){
k-=(dep[x]-dep[top[x]]+1);
x=f[top[x]];
}
return id[dfn[x]-k];
}
int main(){
freopen("T2.txt","r",stdin);
// freopen("civilization.out","w",stdout);
rd(n),rd(m);
for(int i=1,u,v;i<n;++i) rd(u),rd(v),add(u,v),add(v,u);
dfs1(1,0),dfs2(1,1);
for(int i=1;i<=(n<<2);++i) t[i].tg=-1;
while(m--){
int tt,rt;rd(tt),rd(rt);
mdf(1,1,n,1,n,1);
for(int i=2,x,lca,L,R,mid;i<=tt;++i){
rd(x);lca=LCA(rt,x);
L=dep[rt]-dep[lca]-1,R=dep[x]-dep[lca]-1,mid=L+R+1>>1;
if(mid<=R){
mid=jump(x,mid);
mdf(1,1,idx,dfn[mid],dfn[mid]+sz[mid]-1,0);
}
else{
mid=jump(rt,L+R+1-mid);
mdf(1,1,idx,1,dfn[mid]-1,0),
mdf(1,1,idx,dfn[mid]+sz[mid],idx,0);
}
}
printf("%d\n",t[1].sum);
}
return 0;
}