寄。摆。润。
寄
首先套路拆边贡献。那么设 \(dp_{x,i}\) 为在 \(x\) 节点有 \(i\) 个没匹配的最小代价。转移有三种：
- 往上传：树形背包。
- 在 \(x\) 放一个：直接清零。
- 放子树里：这个不太好考虑。
我们这样的话还需要加信息。设 \(g_{x,i}\) 为 \(x\) 子树最近的中转点为 \(i\) 的最小代价，那么转移可以暴力枚举 \(i\)，然后直接枚举子树大小取最小值。复杂度是 \(O(n^2)\) 的。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,c;
struct node{
int v,w,next;
}edge[6010];
int t,head[3010];
void add(int u,int v,int w){
edge[++t].v=v;edge[t].w=w;edge[t].next=head[u];head[u]=t;
}
int dep[3010],size[3010],dp[3010][3010],g[3010][3010];
int dis(int x,int y){
return dep[y]-dep[x];
}
void dfs(int x,int f){
dp[x][0]=c;dp[x][size[x]]=0;
g[x][x]=c;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dep[edge[i].v]=dep[x]+edge[i].w;
dfs(edge[i].v,x);
static int tmp[3010];
for(int j=0;j<=size[x]+size[edge[i].v];j++)tmp[j]=inf;
for(int j=size[x];j>=0;j--){
for(int k=size[edge[i].v];k>=0;k--)tmp[j+k]=min(tmp[j+k],dp[x][j]+dp[edge[i].v][k]+edge[i].w*k);
}
for(int t=1;t<=n;t++){
if(g[x][t]==inf)continue;
int ret=inf;
for(int j=size[edge[i].v];j>=0;j--)ret=min(ret,g[x][t]+dp[edge[i].v][j]+(dis(x,t)+edge[i].w)*j);
tmp[0]=min(tmp[0],ret);
g[x][t]=ret;
}
for(int t=1;t<=n;t++){
if(g[edge[i].v][t]==inf)continue;
int ret=inf;
for(int j=size[x];j>=0;j--)ret=min(ret,g[edge[i].v][t]+dp[x][j]+dis(x,t)*j);
tmp[0]=min(tmp[0],ret);
g[x][t]=ret;
}
size[x]+=size[edge[i].v];
for(int j=0;j<=size[x];j++)dp[x][j]=tmp[j];
}
}
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&c);
for(int i=1;i<n;i++){
int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
for(int i=1;i<=m;i++){
int x;scanf("%lld",&x);size[x]++;
}
memset(dp,0x3f,sizeof(dp));memset(g,0x3f,sizeof(g));
dfs(1,0);
printf("%lld\n",dp[1][0]);
return 0;
}
摆
先特判 \(c=1\)。
发现整个左下角都是一样的，考虑给他消了。每行用上一行减掉本行，那么就形成一个次对角线都是 \(c-1\) 的上 Hessenberg 矩阵。
考虑行列式是怎么算的：枚举排列元素相乘。那么上 Hessenberg 矩阵的这种排列拆成置换环有个性质：一定是连续的一段成环。如果不是，那么会跑到下边的 \(0\) 上，没有贡献。同时，次对角线都是 \(c-1\)，于是我们可以把 \(2-n\) 行都除 \(1-c\) 来使得全是 \(-1\)，消除逆序对的影响。还有一个性质：行 \(i\) 在 \(i\) 之后的位置如果不是 \(0\) 则全是 \(c\)，且它们都在 \(i\) 的因数 \(+1\) 的位置。若设 \(v=\frac c{1-c}\)，那么每个置换环的贡献就都是 \(v\)。于是可以设 \(dp_i\) 为排列考虑到第 \(i\) 个位置的答案，那么枚举上一个置换环的结尾，有转移：
\[dp_i=dp_{i-1}+v\sum_{j|i\wedge j\neq i}dp_j-dp_{j-1} \]把 \(dp_{i-1}\) 挪到左边，发现是对称的差分形式。于是设 \(g_i=dp_i-dp_{i-1}\)，即得到：
\[g_i=v\sum_{j|i\wedge j\neq i}g_j \]只需要对 \(g\) 做前缀和，再乘个 \((1-c)^{n-1}\) 就是答案。那么考虑 \(g\) 的前缀和：
\[\begin{aligned} &\sum_{i=1}^ng_i\\ =&\sum_{i=1}^nv\sum_{j|i\wedge j\neq i}g_j\\ =&1+v\sum_{i=1}^ng_i\left(\left\lfloor\frac ni\right\rfloor-1\right) \end{aligned} \]直接类似杜教筛地递归即可。复杂度 \(O(n^{\frac 23})\)，就完了……吗？
我们发现 \(g\) 不是很好预处理。然而观察性质，发现若 \(n\) 的唯一分解 \(\prod_{i=1}^mp_i^{a_i}\) 中的 \(\{a_i\}\) 集合相同，则 \(g_n\) 是相同的。于是对质数幂做一个哈希就可以找到所有不同的 \(n\)，这个可以线性筛出。找到所有哈希值之后暴力计算 \(g\) 即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <unordered_map>
#define int long long
using namespace std;
const int mod=998244353,prm=131;
int n,c,v,sq;
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
unsigned long long hs[22000010],H[22000010];
int p[2000010],f[22000010],g[22000010];
bool vis[22000010];
unordered_map<unsigned long long,int>mp;
unordered_map<int,int>S;
void get(int n){
for(int i=2;i<=n;i++){
if(!vis[i])p[++p[0]]=i,H[i]=hs[i]=prm;
for(int j=1;j<=p[0]&&i*p[j]<=n;j++){
vis[i*p[j]]=true;
if(i%p[j]==0){
H[i*p[j]]=prm*H[i];
hs[i*p[j]]=hs[i]-H[i]+H[i*p[j]];
break;
}
H[i*p[j]]=H[p[j]];
hs[i*p[j]]=hs[i]+H[p[j]];
}
}
g[1]=1;
for(int i=2;i<=n;i++){
if(mp.find(hs[i])==mp.end()){
int ret=0;
for(int j=1;j*j<=i;j++){
if(i%j==0){
ret=(ret+g[j])%mod;
if(j*j!=i)ret=(ret+g[i/j])%mod;
}
}
ret=1ll*ret*v%mod;
mp[hs[i]]=ret;
}
g[i]=mp[hs[i]];
}
for(int i=1;i<=n;i++)f[i]=(f[i-1]+g[i])%mod;
}
int s(int n){
if(n<=sq)return f[n];
if(S.find(n)!=S.end())return S[n];
int ans=0;
for(int l=1,r;l<=n;l=r+1){
int x=n/l;
if(x==1)break;
r=n/x;
ans=(ans+1ll*(x-1)%mod*(s(r)-s(l-1)+mod))%mod;
}
ans=(1ll*ans*v+1)%mod;
return S[n]=ans;
}
signed main(){
scanf("%lld%lld",&n,&c);sq=pow(n,2.0/3);
if(c==1){
if(n<=2)puts("1");
else puts("0");
return 0;
}
v=1ll*c*qpow(1-c+mod,mod-2)%mod;
get(sq);
int ans=s(n);
ans=1ll*ans*qpow(1-c+mod,(n-1)%(mod-1))%mod;
printf("%lld\n",ans);
return 0;
}
润
考虑一个暴力 dp：对于一段，设 \(dp_{i,0/1}\) 为到第 \(i\) 位，有无进位的答案，那么暴力 \(dp\) 就能做到单次 \(O(n)\)。每次询问把 \(r\) 放在最后一个 \(1\)，那么如果左边第一个 \(1\) 在 \(l\) 前边，说明这是一段 \(0\)，答案容易算出。否则，考虑把答案的贡献按照是否进位 \(x\) 分开：一部分形如对连续的 \((i+1)2^i\) 求和，可以简单计算；另一部分是分出两半对下一层计算，实际上是算到下一层的 \(f_{i+1,0/1}\)，即 \(0/1\) 的贡献和，可以把 \(0,1\) 拆开分别维护。带修上线段树即可，要支持翻转、覆盖、区间和、线段树上二分。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int mod=998244353,inv2=(mod+1)>>1;
int n,m,pw[100010],invpw[100010];
char s[100010];
struct node{
#define lson rt<<1
#define rson rt<<1|1
int l,r,sum,lz,s[2];
bool rev;
}tree[400010];
void pushup(int rt){
tree[rt].sum=tree[lson].sum+tree[rson].sum;
tree[rt].s[0]=(tree[lson].s[0]+tree[rson].s[0])%mod;
tree[rt].s[1]=(tree[lson].s[1]+tree[rson].s[1])%mod;
}
void pushrev(int rt){
if(tree[rt].lz==-1)tree[rt].rev^=1;
else tree[rt].lz^=1;
swap(tree[rt].s[0],tree[rt].s[1]);
tree[rt].sum=tree[rt].r-tree[rt].l+1-tree[rt].sum;
}
void pushtag(int rt,int val){
tree[rt].lz=val;tree[rt].rev=false;
int ret=(tree[rt].s[0]+tree[rt].s[1])%mod;
if(val==0)tree[rt].s[0]=ret,tree[rt].s[1]=tree[rt].sum=0;
else tree[rt].s[1]=ret,tree[rt].s[0]=0,tree[rt].sum=tree[rt].r-tree[rt].l+1;
}
void pushdown(int rt){
if(tree[rt].rev){
pushrev(lson);pushrev(rson);tree[rt].rev=false;
}
if(~tree[rt].lz){
pushtag(lson,tree[rt].lz);pushtag(rson,tree[rt].lz);
tree[rt].lz=-1;
}
}
void build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;tree[rt].lz=-1;
if(l==r){
if(s[l]=='1')tree[rt].sum=1,tree[rt].s[1]=pw[l];
else tree[rt].s[0]=pw[l];
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(rt);
}
void update(int rt,int l,int r){
if(l<=tree[rt].l&&tree[rt].r<=r){
pushrev(rt);return;
}
pushdown(rt);
int mid=(tree[rt].l+tree[rt].r)>>1;
if(l<=mid)update(lson,l,r);
if(mid<r)update(rson,l,r);
pushup(rt);
}
void modify(int rt,int l,int r,int val){
if(l<=tree[rt].l&&tree[rt].r<=r){
pushtag(rt,val);return;
}
pushdown(rt);
int mid=(tree[rt].l+tree[rt].r)>>1;
if(l<=mid)modify(lson,l,r,val);
if(mid<r)modify(rson,l,r,val);
pushup(rt);
}
int querys0(int rt,int l,int r){
if(l<=tree[rt].l&&tree[rt].r<=r)return tree[rt].s[0];
pushdown(rt);
int mid=(tree[rt].l+tree[rt].r)>>1,val=0;
if(l<=mid)(val+=querys0(lson,l,r))%=mod;
if(mid<r)(val+=querys0(rson,l,r))%=mod;
return val;
}
int querys1(int rt,int l,int r){
if(l<=tree[rt].l&&tree[rt].r<=r)return tree[rt].s[1];
pushdown(rt);
int mid=(tree[rt].l+tree[rt].r)>>1,val=0;
if(l<=mid)(val+=querys1(lson,l,r))%=mod;
if(mid<r)(val+=querys1(rson,l,r))%=mod;
return val;
}
int queryR(int rt,int R){
if(R<=0)return 0;
if(tree[rt].r<=R){
if(!tree[rt].sum)return tree[rt].l-1;
if(tree[rt].l==tree[rt].r)return tree[rt].l;
pushdown(rt);
int mid=(tree[rt].l+tree[rt].r)>>1;
if(tree[rson].sum)return queryR(rson,R);
else return queryR(lson,R);
}
pushdown(rt);
int mid=(tree[rt].l+tree[rt].r)>>1,val=0;
if(R>mid)val=queryR(rson,R);
if(!val||val==mid)val=queryR(lson,R);
return val;
}
int dp[100010][2];
int solve(int l,int r){
if(l>r)return 0;
int L=queryR(1,r-1);
if(L<l)return dp[r-l+1][0];
int ret=(1ll*pw[r-l+1]*(r-l+2+r-L+2)%mod*(L-l+1)%mod*inv2)%mod;
ret=(ret+1ll*(1ll*dp[r-L][0]*querys0(1,l,L)+1ll*dp[r-L][1]*querys1(1,l,L))%mod*invpw[l])%mod;
ret=(ret+dp[r-L][0])%mod;
return ret;
}
int main(){
scanf("%d%d%s",&n,&m,s+1);pw[0]=invpw[0]=1;
for(int i=1;i<=n;i++)pw[i]=(pw[i-1]<<1)%mod,invpw[i]=1ll*invpw[i-1]*inv2%mod;
dp[1][0]=1;dp[1][1]=6;
for(int i=2;i<=n;i++){
dp[i][0]=(2ll*dp[i-1][0]+1ll*i*pw[i-1])%mod;
dp[i][1]=(dp[i-1][0]+dp[i-1][1]+1ll*(i+1)*pw[i])%mod;
}
build(1,1,n);
while(m--){
int od,l,r;scanf("%d%d%d",&od,&l,&r);
if(od==1)update(1,l,r);
if(od==2)modify(1,l,r,0);
if(od==3)modify(1,l,r,1);
if(od==4)printf("%d\n",solve(l,queryR(1,r)));
}
return 0;
}