CF1750H BinaryStringForces
1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx 1kri /bx
复读一下 1 老师题解。
摆了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=200005; inline int read(){ int x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } int n,a[N],len[N],f[N],cnt,c[N],L[N]; ll ans; char str[N]; struct Node1{ int mx; }t1[N<<2]; #define ls(x) (x<<1) #define rs(x) (x<<1|1) inline void build(int k,int l,int r){ t1[k].mx=0; if(l==r){ if(!a[l] && a[l+1]) t1[k].mx=l+len[l]; return; } int mid=l+r>>1; build(ls(k),l,mid); build(rs(k),mid+1,r); t1[k].mx=max(t1[ls(k)].mx,t1[rs(k)].mx); } inline void find(int k,int l,int r,int ql,int qr,int x){ if(t1[k].mx<x) return; if(l==r){ c[++cnt]=l; return; } int mid=l+r>>1; if(ql<=mid) find(ls(k),l,mid,ql,qr,x); if(qr>mid) find(rs(k),mid+1,r,ql,qr,x); } int rt[N],tot; struct Node2{ int all,cnt,ls,rs; }t2[N<<6]; inline void pushup(int k){ if(t2[k].all) return; t2[k].cnt=t2[t2[k].ls].cnt+t2[t2[k].rs].cnt; } inline int update(int k,int l,int r,int ql,int qr){ if(t2[k].all) return k; int dir=++tot; t2[tot]=t2[k]; if(l>=ql && r<=qr){ t2[dir].all=1; t2[dir].cnt=r-l+1; return dir; } int mid=l+r>>1; if(ql<=mid) t2[dir].ls=update(t2[dir].ls,l,mid,ql,qr); if(qr>mid) t2[dir].rs=update(t2[dir].rs,mid+1,r,ql,qr); pushup(dir); return dir; } inline int query(int k,int l,int r,int ql,int qr){ if(!k) return 0; if(t2[k].all) return min(qr,r)-max(ql,l)+1; if(l>=ql && r<=qr) return t2[k].cnt; int mid=l+r>>1,ret=0; if(ql<=mid) ret+=query(t2[k].ls,l,mid,ql,qr); if(qr>mid) ret+=query(t2[k].rs,mid+1,r,ql,qr); return ret; } inline void STO_1kri_Orz(){ n=read(); scanf("%s",str+1); for(int i=1;i<=n;i++) a[i]=str[i]-'0'; a[n+1]=1; ans=1ll*n*(n+1)/2; for(int i=1;i<=n;i++) len[i]=(!a[i])?len[i-1]+1:0; build(1,1,n); for(int i=1;i<=n;i++){ if(!a[i] && i>len[i]){ // 钦定 i 作为右端点留下 cnt=0; L[i]=n+1; // i-len[i]-j < len[i] // j > i-2*len[i] // len[j] > i-len[i]-j // j+len[j] > i-len[i] find(1,1,n,max(1,i-2*len[i]+1),i-len[i],i-len[i]+1); if(cnt>0){ L[i]=L[c[1]]; if(cnt>1 && L[c[2]]<=c[1]) rt[i]=rt[c[2]],L[i]=min(L[i],L[c[2]]); // c2 包含 c1 else{ // c1 c2 无交 // i-len[i]-j < j-k+1 // k < 2j+1+len[i]-i rt[i]=update(rt[c[1]],1,n,c[1]-len[c[1]]+1,2*c[1]+len[i]-i); } } // i-len[i]-k+1 < len[i] // k > i-2len[i]+1 L[i]=min(L[i],max(1,i-2*len[i]+2)); if(len[i]>1) rt[i]=update(rt[i],1,n,max(1,i-2*len[i]+2),i-len[i]); } // 在前面枚举最后一个钦定的地方 j+len[j] > i cnt=0; if(i>1) find(1,1,n,1,i-1,i+1); if(!a[i]) c[++cnt]=i; for(int j=1,k=1;j<=cnt;j++){ // k > i-c[j] ans-=len[c[j]]-(i-c[j]); // c[j] : [lst,c[j]-(i-c[j])] ans-=query(rt[c[j]],1,n,k,2*c[j]-i); k=2*c[j]-i+1; } } printf("%lldn",ans); for(int i=1;i<=n;i++) rt[i]=0; for(int i=1;i<=tot;i++) t2[i]={0,0,0,0}; tot=0; } int main(){ int tc=read(); while(tc--) STO_1kri_Orz(); return 0; }
View Code
ARC083F Collecting Balls
首先，我们把支配关系转化到图上，对于在 $(x,y)$ 的球，我们给第 $x$ 行与第 $y$ 列连无向边。
这样我们把问题转化为，我们需要给每条边选一个端点，让这个端点支配这条边。同时，同时如果边 $(u,v)$ 被 $u$ 支配，那么对于所有 $d<v$，$(u,d)$ 必须在 $(u,v)$ 之前被 $d$ 支配。
那么首先，如果这个图不是基环树森林，答案一定为 $0$。
那么现在考虑那个支配顺序关系。考虑对于一棵基环树，如果我们先把环支配好（显然有两种方式，即和环上的支配顺序有关），再按照支配关系连边，那么这又会变成一个内向树森林。
如果我们支配好了每个基环树的环，那么贡献就是整个内向树森林的拓扑序数量，即 $frac{2n!}{prod{siz_i} }$。证明就是因为对于 $i$ 而言，有 $siz_i-1$ 个点不能在它前面，那么合法方案就要乘一个 $frac{1}{siz_i}$ 的系数。
当然直接枚举定向关系再把每种情况的答案加起来复杂度就上天了，这里我们考虑加法原理的本质，即每棵基环树有两种定向方式，设其算出来的系数为
$A,B$，那么我们算完了其它部分的总系数 $T$ 后，合并起来的系数就应该是 $(A+B)T$。因此我们只需要对每棵基环树计算这个系数即可。
精细实现可做到 $O(n)$。
#include<bits/stdc++.h> using namespace std; const int N=200005; const int mod=1000000007; inline int read(){ int x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } int n,fac[N],inv[N],ans; int dfn[N],low[N],idx,bri[N<<1],col[N],tr,ecnt; vector<int>g[N]; int cnt,vis[N],b[N],circnt,iscir[N],ctr[N],cir[N],deg[N],siz[N]; struct Edge{ int to,nxt; }e[N<<1],c[N]; int heade[N],tote,headc[N],totc; inline void adde(int u,int v){ e[++tote]={v,heade[u]}; heade[u]=tote; } inline void addc(int u,int v){ c[++totc]={v,headc[u]}; headc[u]=totc; } inline void tarjan(int u,int fa){ dfn[u]=low[u]=(++idx); for(int i=heade[u];i;i=e[i].nxt){ int v=e[i].to; if(!dfn[v]){ tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) bri[i]=bri[i^1]=1; } else if(v!=fa) low[u]=min(low[u],dfn[v]); } } inline void dfs1(int u,int fa){ col[u]=tr; g[tr].emplace_back(u); for(int i=heade[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa || bri[i]) continue; if(col[v]){ ecnt++; continue; } dfs1(v,u); } } inline void dfs2(int u){ vis[u]=1; b[++cnt]=u; for(int i=heade[u];i;i=e[i].nxt){ int v=e[i].to; if(vis[v]) continue; dfs2(v); } } inline void dfs3(int u,int fa){ for(int i=heade[u];i;i=e[i].nxt){ int v=e[i].to; if(iscir[v] || v==fa) continue; ctr[v]=u; dfs3(v,u); } } inline void dfs4(int u,int fa){ for(int i=heade[u];i;i=e[i].nxt){ int v=e[i].to; if(v>=ctr[u]) continue; addc(u,v); deg[v]++; } for(int i=heade[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa || iscir[v]) continue; dfs4(v,u); } } inline int dfs5(int u,int fa){ siz[u]=1; int res=1; for(int i=headc[u];i;i=c[i].nxt){ int v=c[i].to; if(v==fa) continue; res=1ll*res*dfs5(v,u)%mod; siz[u]+=siz[v]; } res=1ll*res*inv[siz[u]]%mod; return res; } inline int calc(){ for(int i=1;i<=circnt;i++) dfs4(cir[i],-1); int ret=1; for(int i=1;i<=cnt;i++) if(!deg[b[i]]) ret=1ll*ret*dfs5(b[i],-1)%mod; return ret; } inline int solve(int rt){ cnt=circnt=0; dfs2(rt); for(int i=1;i<=cnt;i++) if(iscir[b[i]]) dfs3(b[i],-1),cir[++circnt]=b[i]; for(int i=1;i<=cnt;i++) headc[b[i]]=deg[b[i]]=0; totc=0; for(int i=1;i<circnt;i++) ctr[cir[i]]=cir[i+1]; ctr[cir[circnt]]=cir[1]; int ret=calc(); for(int i=1;i<=cnt;i++) headc[b[i]]=deg[b[i]]=0; totc=0; for(int i=1;i<circnt;i++) ctr[cir[i+1]]=cir[i]; ctr[cir[1]]=cir[circnt]; (ret+=calc())%=mod; return ret; } int main(){ n=read(); tote=1; for(int i=1;i<=n*2;i++){ int u=read(),v=read(); adde(u,v+n); adde(v+n,u); } fac[0]=fac[1]=inv[1]=1; for(int i=2;i<=n*2;i++) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; for(int i=1;i<=n*2;i++) if(!dfn[i]) tarjan(i,-1); for(int i=1;i<=n*2;i++) if(!col[i]){ tr++; ecnt=0; dfs1(i,-1); if(ecnt>2) return puts("0"),0; } for(int i=1;i<=tr;i++){ if(g[i].size()==1) continue; for(int j=0;j<g[i].size();j++) iscir[g[i][j]]=1; } ans=1; for(int i=1;i<=n*2;i++) if(!vis[i]) ans=1ll*ans*solve(i)%mod; ans=1ll*ans*fac[n*2]%mod; printf("%dn",ans); return 0; }
View Code
CF930E Coins Exhibition
看上去不好下手，我们应该从暴力出发。
首先来一个不用脑子的暴力：设 $f_{i,0/1,j}$ 表示处理了前 $i$ 个位置，$a_i=0/1$，且 $j$ 为最近一个满足 $a_j neq a_i$ 的位置的合法方案数。直接做复杂度 $O(k^2)$，肯定是不行的。
当然我们需要离散化一下，改成一段一段区间转移。我们记离散化后第 $i$ 段区间的最后一个位置为 $r_i$。
修改一下 dp 状态：$f_{i,0/1,j}$ 表示处理到第 $i$ 个区间，$a_{r_i}=0/1$， 上一个满足 $a_x neq a_{r_i}$ 的位置 $x$ 处在第 $j$ 个区间的合法方案数。以 $f_{i,0,j}$ 为例，依次考虑以下转移：
1. 整个区间全部填 $0$
$f_{i,0,j} to f_{i+1,0,j}$
2. 整个区间全部填 $1$
$f_{i,0,j} to f_{i+1,1,i}$
3. 区间内有 $0$ 和 $1$，且 $a_{r_i}=0$
$f_{i,0,j} times (2^{len_i-1}-1) to f_{i+1,0,i+1}$
4. 区间内有 $0$ 和 $1$，且 $a_{r_i}=1$
$f_{i,0,j} times (2^{len_i-1}-1) to f_{i+1,1,i+1}$
其中 $len_i$ 表示第 $i$ 段区间的长度。
对于 $f_{i,1,j}$ 的转移是类似的。
再考虑去除掉不合法的方案，每一层 $i$ 转移完后，我们对于形如 $[0/1,x,i+1]$ 的限制，将对应的 $f_{i+1,1/0,j}(j<x)$ 置为 $0$ 即可。此时你应该注意到，我们在离散化时需要将 $x-1$ 也进行离散化，否则 $x$ 之前所在的一段会没有被覆盖到。
这样我们就得到了一个 $O((n+m)^2)$ 的做法。它还是过不了。
但其实接下来的优化是简单的。我们考虑跟随 $i$ 的移动，动态维护整个 dp 过程。对应上面转移的标号：
- 1 和 2 不需要做任何事。
- 3 和 4 事实上是一个 **全局和** 的形式。
- 去除掉不合法的方案相当于前缀推平为 $0$。
这其实都不需要任何数据结构维护了，我们可以直接对于前缀维护推平指针（显然一个位置被推平后就永远都是 $0$ 了），并维护好 $0/1$ 的全局和就可以了。
时间复杂度为 $O((n+m) log (n+m) + (n+m) log k)$，前面是离散化的复杂度，后面是算贡献那里求一个快速幂的复杂度。
#include<bits/stdc++.h> typedef long long ll; using namespace std; const int N=600005; const int mod=1000000007; inline int read(){ int x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } /* dp[i][0/1][j] : 处理到第 i 个区间 sta[r[i]]=0/1 上一个与 sta[r[i]] 不一样的位置在第 j 个区间 1.dp[i][0][j] -> dp[i+1][0][j] 2.dp[i][0][j] -> dp[i+1][1][i] 3.dp[i][0][j]*(2^(len-1)-1) -> dp[i+1][0/1][i+1] 1.dp[i][1][j] -> dp[i+1][1][j] 2.dp[i][1][j] -> dp[i+1][0][i] 3.dp[i][1][j]*(2^(len-1)-1) -> dp[i+1][0/i][i+1] 考虑动态维护 1. 不用动 2. 一个全局和的形式 3. 一个全局和的形式 4. 前缀推平为 0 不需要 ds 就能维护 */ int K,m,n,lcnt,b[N],dp[2][N],sum[2],pos[2]={1,1},ans; struct A{ int l,r; }a[N]; struct Q{ int l,v; }; vector<Q>q[N]; inline int qpow(int y){ int x=2,r=1; while(y){ if(y&1) r=1ll*r*x%mod; x=1ll*x*x%mod; y>>=1; } return r; } int main(){ K=read(),n=read(),m=read(); for(int i=1;i<=n;i++){ a[i].l=read(),a[i].r=read(); b[++lcnt]=a[i].l-1; b[++lcnt]=a[i].l; b[++lcnt]=a[i].r; } for(int i=n+1;i<=n+m;i++){ a[i].l=read(),a[i].r=read(); b[++lcnt]=a[i].l-1; b[++lcnt]=a[i].l; b[++lcnt]=a[i].r; } b[++lcnt]=0; b[++lcnt]=1; b[++lcnt]=K; sort(b+1,b+lcnt+1); lcnt=unique(b+1,b+lcnt+1)-b-1; for(int i=1;i<=n+m;i++){ int j=lower_bound(b+1,b+lcnt+1,a[i].r)-b,k=lower_bound(b+1,b+lcnt+1,a[i].l)-b; q[j].emplace_back(Q{k,(i>n)}); } /* f[1][0][1]=1; for(int i=1;i<lcnt;i++){ int siz=b[i+1]-b[i],val=(qpow(siz-1)+mod-1)%mod; for(int j=1;j<=i;j++){ (f[i+1][0][j] += f[i][0][j]) %= mod; (f[i+1][1][i] += f[i][0][j]) %= mod; (f[i+1][0][i+1] += 1ll*val*f[i][0][j]%mod) %= mod; (f[i+1][1][i+1] += 1ll*val*f[i][0][j]%mod) %= mod; (f[i+1][1][j] += f[i][1][j]) %= mod; (f[i+1][0][i] += f[i][1][j]) %= mod; (f[i+1][1][i+1] += 1ll*val*f[i][1][j]%mod) %= mod; (f[i+1][0][i+1] += 1ll*val*f[i][1][j]%mod) %= mod; } for(int j=0;j<q[i+1].size();j++) for(int k=0;k<q[i+1][j].l;k++) f[i+1][q[i+1][j].v^1][k]=0; } for(int j=1;j<=lcnt;j++) (ans += (f[lcnt][0][j]+f[lcnt][1][j])%mod ) %= mod; printf("%dn",ans); */ dp[0][1]=sum[0]=1; for(int i=1;i<lcnt;i++){ int siz=b[i+1]-b[i],val=(qpow(siz-1)+mod-1)%mod,tot=(sum[0]+sum[1])%mod; (dp[0][i] += sum[1]) %= mod; (dp[0][i+1] += 1ll*tot*val%mod) %= mod; (dp[1][i] += sum[0]) %= mod; (dp[1][i+1] += 1ll*tot*val%mod) %= mod; int nxt = ( (sum[0] + sum[1]) % mod + 1ll*tot*val%mod ) % mod; sum[0]=sum[1]=nxt; for(int j=0;j<q[i+1].size();j++){ int op=q[i+1][j].v^1; while(pos[op]<q[i+1][j].l) (sum[op]+=mod-dp[op][pos[op]])%=mod,dp[op][pos[op]]=0,pos[op]++; } } for(int j=1;j<=lcnt;j++) (ans += (dp[0][j]+dp[1][j])%mod ) %= mod; printf("%dn",ans); return 0; }
原文链接: https://www.cnblogs.com/DitaMirika/p/17089621.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/315881
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
