6.17 冲刺国赛模拟 20
T1 树染色
容易发现每种方案都可以变成没有交边的链剖分，在此基础上的方案数是每个链顶的深度，考虑 DP。
直接 DP 大致是维护 \(\prod (\prod a+\prod b)\times dep_{top}\)，发现这个东西非常不好转移，转移时需要枚举叶子，复杂度不优秀。
改为设 \(f_{i,0/1}\) 表示从 \(i\) 节点连出的链颜色，这样我们就可以直接枚举 \(u\) 链连入的子树 \(v\)，而其他子树的颜色就可以任意选了，这个处理可以先求出所有都任选的个数，再具体计算的时候除去就行了，注意到一个子树内答案是包括顺序的，因此合并子树信息是多重集组合数。
点击查看代码
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
int n;
int inv[maxn],fact[maxn],fact_inv[maxn];
inline int C(int N,int M){
return 1ll*fact[N]*fact_inv[M]%mod*fact_inv[N-M]%mod;
}
struct edge{
int to,nxt,a,b;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v,int a,int b){
e[++cnt].to=v,e[cnt].nxt=head[u],e[cnt].a=a,e[cnt].b=b,head[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=head[v],e[cnt].a=a,e[cnt].b=b,head[v]=cnt;
}
int dep[maxn],siz[maxn];;
int f[maxn][2];
void dfs(int u,int fa,int d){
dep[u]=d;
int prodf=1,prodC=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,a=e[i].a,b=e[i].b;
if(v==fa) continue;
dfs(v,u,d+1);
siz[u]+=siz[v];
prodf=1ll*prodf*(1ll*f[v][0]*a%mod+1ll*f[v][1]*b%mod)%mod*(dep[u]+1)%mod;
prodC=1ll*prodC*fact_inv[siz[v]]%mod;
}
if(!siz[u]){
siz[u]=1;
f[u][0]=f[u][1]=1;
return;
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,a=e[i].a,b=e[i].b;
if(v==fa) continue;
int nowf=1ll*prodf*q_pow((1ll*f[v][0]*a%mod+1ll*f[v][1]*b%mod)%mod*(dep[u]+1)%mod,mod-2,mod)%mod,nowC=1ll*prodC*fact[siz[u]-1]%mod*siz[v]%mod;
f[u][0]=(f[u][0]+1ll*f[v][0]*a%mod*nowf%mod*nowC%mod)%mod;
f[u][1]=(f[u][1]+1ll*f[v][1]*b%mod*nowf%mod*nowC%mod)%mod;
}
}
int main(){
freopen("treecolor.in","r",stdin);
freopen("treecolor.out","w",stdout);
n=read();
inv[1]=1;
for(int i=2;i<=n;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
fact[0]=1;
for(int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%mod;
fact_inv[0]=1;
for(int i=1;i<=n;++i) fact_inv[i]=1ll*fact_inv[i-1]*inv[i]%mod;
for(int i=1;i<n;++i){
int u=read(),v=read(),a=read(),b=read();
add_edge(u,v,a,b);
}
dfs(1,0,0);
printf("%d\n",(f[1][0]+f[1][1])%mod);
return 0;
}
T2 关路灯
发现如果不考虑询问区间的限制，每次改变方向后移动的距离一定大于上次一定总距离的 \(2\) 倍，也就是只会改变 \(O(\log n)\) 次方向，考虑由右到左的条件是 \(a_x-a_{l-1}<a_{x+1}-a_x\)，由左到右的条件是 \(a_{r+1｝-a_x\ge a_x-a_{x-1}\)，整理完是就是找到第一个满足条件的 \(x\)，可以二分区间，用 ST 表查最值。
有了区间询问的限制实际上就是第一个超出区间的拐点会变成这个区间的端点，之后再转向就直接走到另一个端点了，因此我们可以计算每个询问区间中的每个位置究竟是先到达哪个端点。
以右端点贡献为例，在初始位置 \(s\) 把左端点加入，这里只加入从左向右的线段，之后每次遇到线段右端点就删除这条线段，进而加入下一条 \(s\) 相同的从左到右的线段，删除前如果当前位置有询问区间右端点就线段树上查询。注意到如果右端点贡献则说明存在一个线段右端点在询问的右侧，但这个线段并不覆盖询问区间，所以就是查询左端点小于询问区间左端点的相关信息，线段树维护答案即可。左端点贡献同理。复杂度 \(O(n\log^2 n+m\log n)\)。
点击查看代码
int n,m;
int a[maxn];
int L[maxm],R[maxm];
int stmx[maxn][maxlog],stmn[maxn][maxlog];
inline void build(){
for(int i=1;i<=n;++i){
stmx[i][0]=(i==1)?inf:2*a[i]-a[i-1];
stmn[i][0]=(i==n)?-inf:2*a[i]-a[i+1];
}
for(int k=1;k<=18;++k){
for(int i=1;i+(1<<k)-1<=n;++i){
stmx[i][k]=max(stmx[i][k-1],stmx[i+(1<<k-1)][k-1]);
stmn[i][k]=min(stmn[i][k-1],stmn[i+(1<<k-1)][k-1]);
}
}
}
inline int query_max(int l,int r){
int k=__lg(r-l+1);
return max(stmx[l][k],stmx[r-(1<<k)+1][k]);
}
inline int query_min(int l,int r){
int k=__lg(r-l+1);
return min(stmn[l][k],stmn[r-(1<<k)+1][k]);
}
struct Segment{
int bel;
int id,l,r;
ll len;
bool type;
Segment()=default;
Segment(int bel_,int id_,int l_,int r_,ll len_,bool type_):bel(bel_),id(id_),l(l_),r(r_),len(len_),type(type_){}
};
vector<Segment> Seg[maxn],LS[maxn],RS[maxn];
vector<int> Q[maxn];
struct Data{
int siz;
ll sum1,sum2;
Data()=default;
Data(int siz_,ll sum1_,ll sum2_):siz(siz_),sum1(sum1_),sum2(sum2_){}
Data operator+(const Data& rhs)const{
return Data(siz+rhs.siz,sum1+rhs.sum1,sum2+rhs.sum2);
}
};
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
Data val[maxn<<2];
inline void push_up(int rt){
val[rt]=val[rt<<1]+val[rt<<1|1];
}
void update(int rt,int l,int r,int p,int k1,int k2,int k3){
if(l==r){
val[rt].siz+=k1,val[rt].sum1+=k2,val[rt].sum2+=k3;
return;
}
if(p<=mid) update(lson,p,k1,k2,k3);
else update(rson,p,k1,k2,k3);
push_up(rt);
}
Data query(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return val[rt];
Data res=Data(0,0,0);
if(pl<=mid) res=res+query(lson,pl,pr);
if(pr>mid) res=res+query(rson,pl,pr);
return res;
}
void clear(int rt,int l,int r){
val[rt]=Data(0,0,0);
if(l==r) return;
clear(lson),clear(rson);
}
#undef mid
#undef lson
#undef rson
}S;
ll ans[maxm];
int main(){
freopen("light.in","r",stdin);
freopen("light.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i) a[i]=read();
build();
for(int i=1;i<=m;++i) L[i]=read(),R[i]=read();
for(int i=1;i<=n;++i){
int lpos=i,rpos=i;
if(i==1){
Seg[i].push_back(Segment(i,0,1,1,0,0));
Seg[i].push_back(Segment(i,1,1,n,0,1));
continue;
}
if(i==n){
Seg[i].push_back(Segment(i,0,n,n,0,1));
Seg[i].push_back(Segment(i,1,1,n,0,0));
continue;
}
bool type=(a[i+1]-a[i]<=a[i]-a[i-1]);
Seg[i].push_back(Segment(i,0,i,i,0,type^1));
int cnt=0;
ll sum=0;
while(1){
if(type){
int l=rpos+1,r=n;
int now;
while(l<=r){
int mid=(l+r)>>1;
if(query_min(rpos+1,mid)<a[lpos-1]) now=mid,r=mid-1;
else l=mid+1;
}
rpos=now;
++cnt;
Seg[i].push_back(Segment(i,cnt,lpos,rpos,sum,type));
sum+=a[rpos]-a[lpos];
if(rpos==n){
++cnt;
Seg[i].push_back(Segment(i,cnt,1,n,sum,type^1));
sum+=a[rpos]-a[lpos];
break;
}
rpos=now;
}
else{
int l=1,r=lpos-1;
int now;
while(l<=r){
int mid=(l+r)>>1;
if(query_max(mid,lpos-1)>=a[rpos+1]) now=mid,l=mid+1;
else r=mid-1;
}
lpos=now;
++cnt;
Seg[i].push_back(Segment(i,cnt,lpos,rpos,sum,type));
sum+=a[rpos]-a[lpos];
if(lpos==1){
++cnt;
Seg[i].push_back(Segment(i,cnt,1,n,sum,type^1));
sum+=a[n]-a[1];
break;
}
}
type^=1;
}
}
for(int i=1;i<=n;++i){
if(Seg[i][0].type){
LS[Seg[i][0].l].push_back(Seg[i][0]);
RS[Seg[i][0].r].push_back(Seg[i][0]);
}
else{
LS[Seg[i][1].l].push_back(Seg[i][1]);
RS[Seg[i][1].r].push_back(Seg[i][1]);
}
}
for(int i=1;i<=m;++i){
Q[R[i]].push_back(i);
}
for(int i=1;i<=n;++i){
for(Segment s:LS[i]){
S.update(1,1,n,i,1,a[s.l],s.len);
}
for(int j:Q[i]){
if(L[j]<n){
Data now=S.query(1,1,n,L[j]+1,n);
ans[j]+=1ll*now.siz*(a[R[j]]-a[L[j]]);
ans[j]+=1ll*now.siz*a[R[j]]-now.sum1;
ans[j]+=now.sum2;
}
}
for(Segment s:RS[i]){
S.update(1,1,n,s.l,-1,-a[s.l],-s.len);
if(s.id+2<Seg[s.bel].size()){
Segment nxt=Seg[s.bel][s.id+2];
S.update(1,1,n,nxt.l,1,a[nxt.l],nxt.len);
RS[nxt.r].push_back(nxt);
}
}
}
S.clear(1,1,n);
for(int i=1;i<=n;++i){
LS[i].clear();
RS[i].clear();
Q[i].clear();
}
for(int i=1;i<=n;++i){
if(!Seg[i][0].type){
LS[Seg[i][0].l].push_back(Seg[i][0]);
RS[Seg[i][0].r].push_back(Seg[i][0]);
}
else{
LS[Seg[i][1].l].push_back(Seg[i][1]);
RS[Seg[i][1].r].push_back(Seg[i][1]);
}
}
for(int i=1;i<=m;++i){
Q[L[i]].push_back(i);
}
for(int i=n;i>=1;--i){
for(Segment s:RS[i]){
S.update(1,1,n,i,1,a[s.r],s.len);
}
for(int j:Q[i]){
if(R[j]>1){
Data now=S.query(1,1,n,1,R[j]-1);
ans[j]+=1ll*now.siz*(a[R[j]]-a[L[j]]);
ans[j]+=now.sum1-1ll*now.siz*a[L[j]];
ans[j]+=now.sum2;
}
}
for(Segment s:LS[i]){
S.update(1,1,n,s.r,-1,-a[s.r],-s.len);
if(s.id+2<Seg[s.bel].size()){
Segment nxt=Seg[s.bel][s.id+2];
S.update(1,1,n,nxt.r,1,a[nxt.r],nxt.len);
LS[nxt.l].push_back(nxt);
}
}
}
for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
return 0;
}
T3 树状数组
和 \(r\) 比较大小可以考虑二进制比较 \(\mathrm{lcp}\) 后一位，钦定某个位置是 \(0\) 后计算答案容易想到前后缀拼起来。
剩下这个很梦幻，由于每次操作是对最低位，设 \(f_{i,j,k}\) 为前 \(i\) 次操作得到的所有数中与 \(r\) 在 \(2^j\) 位失配，且在 \([0,j)\) 次二进制位上 \(1\) 的个数是 \(k\) 的方案数。
转移朴素就是对 \(k\) 做加减法，\(k=0\) 或 \(k=j\) 的情况对应的数是唯一的，可以直接暴力算出来，于是可以预处理出转移指针。
这样 \(f\) 也就是前缀就好算了。
后缀 \(g\) 先考虑把 \([0,r]\) 对应状态值设为 \(1\)，之后并不是复刻 \(f\) 的过程，这部分实际是在 DP 系数，也就类似 \(g_{i,j,k}\) 表示此状态对所有合法 \(f\) 总共贡献多少，所以初始点值都是 \(1\)。之后在模仿 \(f\) DP 就行了。复杂度是 \(O(nk^2)\)。
点击查看代码
inline int lowbit(int x){
return x&-x;
}
int n,k,r;
char s[maxn];
int id[maxlog][maxlog],tot;
pii mp[maxlog*maxlog];
int trans[maxlog*maxlog][2];
inline int get_state(int x){
for(int i=k-1;i>=0;--i){
if((r^x)&(1<<i)){
int j=__builtin_popcount(x&((1<<i)-1));
return id[i][j];
}
}
return tot;
}
inline int opt0(int x){
return x-lowbit(x);
}
inline int opt1(int x){
return x+lowbit((1<<k)-1-x);
}
int f[maxn][maxlog*maxlog],g[maxn][maxlog*maxlog];
int main(){
freopen("fenwick.in","r",stdin);
freopen("fenwick.out","w",stdout);
n=read(),k=read(),r=read();
scanf("%s",s+1);
for(int i=0;i<k;++i){
for(int j=0;j<=i;++j){
id[i][j]=++tot;
mp[tot]=make_pair(i,j);
// cerr<<"id:"<<id[i][j]<<" i:"<<i<<" j:"<<j<<endl;
}
}
id[k][0]=++tot;
mp[tot]=make_pair(k,0);
for(int i=0;i<k;++i){
for(int j=0;j<=i;++j){
if(!j){
int now=((r>>i)^1)<<i;
trans[id[i][j]][0]=get_state(opt0(now));
}
else{
trans[id[i][j]][0]=id[i][j-1];
}
if(j==i){
int now=(((r>>i)^1)<<i)|((1<<i)-1);
trans[id[i][j]][1]=get_state(opt1(now));
}
else trans[id[i][j]][1]=id[i][j+1];
// cerr<<"i:"<<i<<" j:"<<j<<" trans0:"<<trans[id[i][j]][0]<<" trans1:"<<trans[id[i][j]][1]<<endl;
}
}
trans[tot][0]=get_state(opt0(r)),trans[tot][1]=get_state(opt1(r));
// cerr<<"i:"<<k<<" j:"<<0<<" trans0:"<<trans[id[k][0]][0]<<" trans1:"<<trans[id[k][0]][1]<<endl;
f[0][get_state(0)]=1;
for(int i=1;i<=n;++i){
for(int j=1;j<=tot;++j){
if(s[i]!='1'){
f[i][trans[j][0]]=(f[i][trans[j][0]]+f[i-1][j])%mod;
}
if(s[i]!='0'){
f[i][trans[j][1]]=(f[i][trans[j][1]]+f[i-1][j])%mod;
}
}
}
for(int i=0;i<=r;++i) g[n+1][get_state(i)]=1;
for(int i=n;i>=1;--i){
for(int j=1;j<=tot;++j){
if(s[i]!='1'){
g[i][j]=(g[i][j]+g[i+1][trans[j][0]])%mod;
}
if(s[i]!='0'){
g[i][j]=(g[i][j]+g[i+1][trans[j][1]])%mod;
}
// cerr<<"i:"<<i<<" j:"<<j<<" g:"<<g[i][j]<<endl;
}
}
for(int i=1;i<=n;++i){
if(s[i]=='1') printf("0\n");
else{
int ans=0;
for(int j=1;j<=tot;++j){
ans=(ans+1ll*f[i-1][j]*g[i+1][trans[j][0]]%mod)%mod;
// cerr<<"f:"<<f[i-1][j]<<" g:"<<g[i+1][trans[j][0]]<<endl;
}
printf("%d\n",ans);
}
}
return 0;
}