从前有一个叫做LL的人,
他由于太蒟蒻了
很悲伤
推出了式子,不会组合数线性求法
写了个n^2dp 炸了
有点痛
#include<bits/stdc++.h> #define ll long long using namespace std; template<typename T>inline void rd(T&x) { char c;bool f=0; while((c=getchar())<‘0‘||c>‘9‘)if(c==‘-‘)f=1; x=c^48; while((c=getchar())>=‘0‘&&c<=‘9‘)x=x*10+(c^48); if(f)x=-x; } const int maxn=1e7+5,mod=1e9+7; int inv[maxn]; inline int pow(int a,int x) { int ret=1; while(x) { if(x&1)ret=1ll*ret*a%mod; x>>=1; a=1ll*a*a%mod; } return ret; } int main() { int n,pa,pb,qa,qb,invb; // freopen("in.txt","r",stdin); rd(n); rd(pa),rd(pb),rd(qa),rd(qb); if(pa==pb) { ll x=pow(qa,n); ll y=pow(qb,n); invb=pow(qb,(int)(1ll*n*(mod-2)%(mod-1))); printf("%lld",1ll*invb*(y-x+mod)%mod); } else if(!qa) { ll x=pow(pb-pa,n); ll y=pow(pb,n); invb=pow(pb,(int)(1ll*n*(mod-2)%(mod-1))); printf("%lld",1ll*(y-x+mod)%mod*invb%mod); } else if(!pa||qa==qb) { printf("0"); } else { inv[1]=inv[0]=1; for(register int i=2;i<=n;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; invb=pow((int)(1ll*pb*qb%mod),(int)(1ll*n*(mod-2)%(mod-1))); int P=pow(pb-pa,mod-2),Q=pow(qb-qa,mod-2); int lastq=pow(qb-qa,n),lastp=1ll*pa*pow(pb-pa,n-1)%mod; int sum=lastq,C=n,ans=(ans+1ll*sum*C%mod*lastp%mod)%mod; for(register int i=2;i<=n;++i) { lastp=1ll*lastp*pa%mod*P%mod; lastq=1ll*lastq*qa%mod*Q%mod; sum=(sum+1ll*lastq*C)%mod; C=1ll*C*(n-i+1)%mod*inv[i]%mod; ans=(ans+1ll*sum*C%mod*lastp)%mod; } printf("%d",1ll*ans*invb%mod); } return 0; }
虽然明知道是树剖
还是很暴力地用十分钟写了个Lca倍增
#include<bits/stdc++.h> #define re return #define inc(i,l,r) for(int i=l;i<=r;++i) using namespace std; template<typename T>inline void rd(T&x) { char c;bool f=0; while((c=getchar())<‘0‘||c>‘9‘)if(c==‘-‘)f=1; x=c^48; while((c=getchar())>=‘0‘&&c<=‘9‘)x=x*10+(c^48); if(f)x=-x; } const int maxn=5e5+5; int n,m,k=1,tot,son[maxn],top[maxn],rev[maxn],fa[maxn]; int hd[maxn],deep[maxn],siz[maxn],seg[maxn],he[maxn]; struct node{ int to,nt; }e[maxn<<1]; inline void add(int x,int y) { e[++k].to=y;e[k].nt=hd[x];hd[x]=k; e[++k].to=x;e[k].nt=hd[y];hd[y]=k; } inline void dfs(int x) { deep[x]=deep[fa[x]]+(siz[x]=1); for(int i=hd[x];i;i=e[i].nt) { int v=e[i].to; if(v==fa[x])continue; fa[v]=x; dfs(v); siz[x]+=siz[v]; if(siz[v]>siz[son[x]]) son[x]=v; } } inline void dfs2(int x,int ftop) { top[x]=ftop; seg[x]=++tot; rev[tot]=x; if(son[x]) { dfs2(son[x],ftop); for(int i=hd[x];i;i=e[i].nt) { int v=e[i].to; if(!top[v]) dfs2(v,v); } } } int sum[maxn<<2],lazy[maxn<<2]; #define ls rt<<1 #define rs rt<<1|1 inline void pushup(int rt) { sum[rt]=sum[ls]+sum[rs]; } inline void pushdown(int rt,int l,int r,int mid) { lazy[ls]=lazy[rs]=lazy[rt]; if(lazy[rt]==1) sum[ls]=mid-l+1,sum[rs]=r-mid; else sum[ls]=sum[rs]=0; lazy[rt]=0; } inline void build(int rt,int l,int r) { if(l==r) { sum[rt]=1; re ; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); pushup(rt); } inline void modify(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y) { sum[rt]=0; lazy[rt]=2; re ; } int mid=(l+r)>>1; if(lazy[rt])pushdown(rt,l,r,mid); if(x<=mid)modify(ls,l,mid,x,y); if(y>mid)modify(rs,mid+1,r,x,y); pushup(rt); } inline int LCA(int x,int y) { while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]])x^=y^=x^=y; x=fa[top[x]]; } re deep[x]<deep[y]?x:y; } inline int jump(int x,int dis) { while(dis&&dis>=deep[x]-deep[fa[top[x]]]) { dis-=(deep[x]-deep[fa[top[x]]]); x=fa[top[x]]; } re rev[seg[x]-dis]; } int main() { int x,y,rt,k; rd(n),rd(m); inc(i,2,n) { rd(x),rd(y); add(x,y); } fa[1]=1; dfs(1); dfs2(1,1); build(1,1,n); inc(i,1,m) { lazy[1]=1; sum[1]=n; rd(k); rd(rt); inc(j,1,k-1) { rd(x); int lca=LCA(x,rt); int left=deep[rt]-deep[lca],right=deep[x]-deep[lca]; if(left<=right) { int v=jump(x,(left+right-1)>>1); modify(1,1,n,seg[v],seg[v]+siz[v]-1); } else { int v=jump(rt,(left+right)>>1); modify(1,1,n,1,seg[v]-1); modify(1,1,n,seg[v]+siz[v],n); } } printf("%d\n",sum[1]); } re 0; }
渣渣辉……
暴力背包合并+单调队列
#include<bits/stdc++.h> #define re return #define ll long long #define dec(i,l,r) for(int i=l;i>=r;--i) #define inc(i,l,r) for(int i=l;i<=r;++i) using namespace std; template<typename T>inline void rd(T&x) { char c;bool f=0; while((c=getchar())<‘0‘||c>‘9‘)if(c==‘-‘)f=1; x=c^48; while((c=getchar())>=‘0‘&&c<=‘9‘)x=x*10+(c^48); if(f)x=-x; } const int N=5e4+10; int P; struct node{ int w,v; node(int ww=0,int vv=0){ w=ww;v=vv; } }Q[N]; struct quu { ll top,f[N][505]; node g[N]; inline void init() { top=f[0][0]=0; inc(i,1,P-1)f[0][i]=-1147483647; } inline void push(node x) { g[++top]=x; inc(i,0,P-1) f[top][(i+x.w)%P]=max(f[top-1][(i+x.w)%P],f[top-1][i]+x.v); } }L,R; inline void rebuild() { int r=0; dec(i,L.top,1)Q[++r]=L.g[i]; inc(i,1,R.top)Q[++r]=R.g[i]; L.init();R.init(); //重新初始化 int mid=r>>1; dec(i,mid,1) L.push(Q[i]); inc(i,mid+1,r)R.push(Q[i]); } inline int Next(int x){re x>0?x-1:P-1;} inline bool check_in(int x,int l,int r) { if(l<=r){re (x>=l&&x<=r);} else re x>=l||x<=r; } int q[1005]; inline void query(int l,int r) { int head=1,tail=0; ll ans=-1; dec(i,r,l) { while(head<=tail&&L.f[L.top][i]>=L.f[L.top][q[tail]])--tail; q[++tail]=i; ans=max(ans,L.f[L.top][i]+R.f[R.top][0]); } //初始化单调序列 l=Next(l),r=Next(r); for(int i=1;i<=P-1;++i,l=Next(l),r=Next(r)) { while(head<=tail&&(!check_in(q[head],l,r)))++head; while(head<=tail&&L.f[L.top][l]>=L.f[L.top][q[tail]])--tail; q[++tail]=l; ans=max(ans,L.f[L.top][q[head]]+R.f[R.top][i]); } if(ans<0) printf("-1\n"); else printf("%lld\n",ans); re ; } int m; int main() { //freopen("in.txt","r",stdin); int test_id,x,y; rd(test_id);//输入测试数据编号 rd(m),rd(P);//操作数以及模数 L.init(),R.init();//左右区间初始化 char opt[20]; inc(i,1,m) { scanf("%s",opt); if(opt[0]==‘I‘&&opt[1]==‘F‘) { rd(x),rd(y); L.push((node){x,y});//左端进入 } else if(opt[0]==‘I‘)//右端加入 { rd(x),rd(y); R.push((node){x,y}); } else if(opt[0]==‘D‘&&opt[1]==‘F‘)//左端弹出 { if(!L.top)rebuild();//没有了。暴力重构 if(L.top)--L.top;//有直接减 else --R.top; } else if(opt[0]==‘D‘) { if(!R.top) rebuild(); if(R.top)--R.top;//其实Rebuild后R.top还等于0应该是不存在的 else --L.top; } else { rd(x),rd(y); //查询 query(x,y); } } re 0; }
——九月22日考试有感
原文:https://www.cnblogs.com/lsyyy/p/11587609.html