22/01/21 yyq 的辛丑年末群友胡策 题解
比赛链接
跟洛谷月赛正好撞了，所以很多群友没来打，有点可惜。
不过学长 sxw 竟然也来参加了这场比赛（虽然来秒了一道题就润了），令人很是惊喜。
题目来源：2019 山东二轮省集
我手头只有题面和数据，原题解我全找不着了，所以只好自己写题解。
T1
原题：D3T1 啊孤独感放辣椒
折半，在两侧分别枚举子集。则合并信息时需要满足的条件是 \(A_1+A_2\leq B_1+B_2\leq C_1+C_2\)。
拆出来三个不等式，其中有一个没有用处。
剩下的两个不等式实际上就是二维偏序，一维双指针，另一维用随便什么数据结构维护区间最小值即可。
代码（我赛时写的）：
//什么时候我才能有杜爷一半强啊/kk
#include
#include
#define lg(x) (31-__builtin_clz(x))
#define int long long
using namespace std;
const int N=25,V=5000086,INF=1e18;
int n,tot,cnt1,cnt2,ans=INF;
int a[N],sum[1<'9'){if(ch=='-')ssss*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
return nn*ssss;
}
bool build(int k,int l,int r){
mn[k]=INF;if(l==r)return true;
int mid=(l+r)>>1;return build(k<<1,l,mid)|build(k<<1|1,mid+1,r);
}
int ask(int k,int l,int r,int x,int y){
if(l>=x&&r<=y)return mn[k];
int mid=(l+r)>>1,ret=INF;
if(x<=mid)ret=Min(ret,ask(k<<1,l,mid,x,y));
if(mid>1;
if(x<=mid)return change(k<<1,l,mid,x,y);
return change(k<<1|1,mid+1,r,x,y);
}
signed main(){
// freopen("ex_A.in","r",stdin);
n=read();for(int i=0;i T2
原题：D8T2 B
还以为是什么牛逼 \(\text{polylog}\) 做法，没想到是根号 \(\log\)。
这道题可以看作是 LNOI 某经典题的带修版本，考虑沿用那题的思路。
我们把所有点按照序号分块，对每一个块维护块内结点到根节点距离之和；开 \(\frac{n}{B}\) 个树状数组，以 \(\text{DFS}\) 序为下标，维护每一层的结点信息。
这里的“结点信息”就是和 LNOI 那道题里需要维护的信息很相似的东西，需要注意的是这题的路径需要带权。初始时这个东西可以 \(\text{DFS}\) 递推出来，然后修改操作就是在做子树加。有了这两个东西，整块就很好处理了。
对于散块其实也很简单，再开一棵树状数组，维护每个点到根节点的距离即可。修改仍然是子树加。
代码（我赛后补的）：
#include
#include
#include
#include
#include
#define int long long
#define lg(x) (31-__builtin_clz(x))
using namespace std;
const int N=60086,BC=251;
int n,m,dfncnt,len,B,T,tot,lans;
int h[N],dfn[N],dis[N],dfr[N],dfa[N],bl[N],el[N],er[N],eu[N],ev[N],ew[N],euler[N<<1][18];
int L[BC],R[BC],sum[BC],cnt[BC][N];
struct edge{int v,w,nxt;}e[N<<1];
struct BIT{
int sze,c[N];
int lowbit(int x){return x&(-x);}
bool build(int x){sze=x;for(int i=1;i<=sze;i++)c[i]=0;return true;}
bool updata(int pos,int num){while(pos<=sze)c[pos]+=num,pos+=lowbit(pos);return true;}
bool add(int l,int r,int z){updata(l,z);updata(r+1,-z);return true;}
int query(int pos){int ret=0;while(pos)ret+=c[pos],pos-=lowbit(pos);return ret;}
}t1,t2[BC];
bool Swap(int &a,int &b){a^=b^=a^=b;return true;}
int Min(int a,int b){return ab?a:b;}
int read(){
char ch=getchar();int nn=0,ssss=1;
while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
return nn*ssss;
}
int gc(){char ch=getchar();while(ch!='m'&&ch!='q')ch=getchar();return ch=='q';}
bool add(int u,int v,int w){e[++tot].v=v;e[tot].w=w;e[tot].nxt=h[u];h[u]=tot;return true;}
bool dfs(int np,int lst){
dfn[np]=++dfncnt;dfa[dfncnt]=np;euler[++len][0]=dfncnt;el[np]=len;cnt[bl[np]][np]++;
for(int i=h[np];i;i=e[i].nxt){
if(e[i].v==lst)continue;if(ev[e[i].w]==np)Swap(eu[e[i].w],ev[e[i].w]);
dis[e[i].v]=dis[np]+ew[e[i].w];dfs(e[i].v,np);euler[++len][0]=dfn[np];
for(int j=1;j<=T;j++)cnt[j][np]+=cnt[j][e[i].v];
}
er[np]=len;dfr[np]=dfncnt;return true;
}
bool dfs2(int np,int lst,int flr){
for(int i=h[np];i;i=e[i].nxt){
if(e[i].v==lst)continue;
int delta=ew[e[i].w]*cnt[flr][e[i].v];
dis[e[i].v]=dis[np]+delta;sum[flr]+=delta;
dfs2(e[i].v,np,flr);
}
return true;
}
int qmin(int l,int r){int lo=lg(r-l+1);return Min(euler[r][lo],euler[l+(1<er[y])Swap(x,y);return dfa[qmin(el[x],er[y])];}
signed main(){
n=read();m=read();int typ=read();t1.build(n);
for(int i=1;i=bl[r])
for(int i=l;i<=r;i++)
lans+=t1.query(dfn[i])-(t1.query(dfn[lca(i,x)])<<1);
else{
for(int i=l;i<=R[bl[l]];i++)lans+=t1.query(dfn[i])-(t1.query(dfn[lca(i,x)])<<1);
for(int i=L[bl[r]];i<=r;i++)lans+=t1.query(dfn[i])-(t1.query(dfn[lca(i,x)])<<1);
for(int i=bl[l]+1;i T3
原题：D9T2 B
上图为杜爷八百年前对这题用到的思路作出的评价。
\(l^k\) 展开为 \(\sum\limits_{i\geq0}{k\brace i}i!\binom{l}{i}\)，交换求和顺序，在每个点对这个式子的每一层 \(i\) 分别维护。转移用二项式系数的递推式，直接拓扑排序即可。
\(O((n+m)k)\)，\(\text{1s}\) 时限有点卡常，但是原题就是这个时限，我没改。
代码（我赛时写的）：
//什么时候我才能有杜爷一半强啊/kk
#include
#include
using namespace std;
const int N=100086,M=200086,K=514,MOD=998244353;
int n,m,k,tot,deg[N],h[N],q[N],f[N][K],s[K][K],fac[K];
struct edge{int v,nxt;}e[M];
inline int Add(int &a,int b){return(a+=b)>=MOD?a-=MOD:a;}
inline int vAdd(int a,int b){return(a+=b)>=MOD?a-=MOD:a;}
inline int Sub(int &a,int b){return(a-=b)<0?a+=MOD:a;}
inline int vSub(int a,int b){return(a-=b)<0?a+=MOD:a;}
inline int Mul(int a,int b){return 1ll*a*b%MOD;}
inline int qpow(int a,int b){
int ret=1;
while(b){if(b&1)ret=Mul(ret,a);a=Mul(a,a);b>>=1;}
return ret;
}
inline int read(){
char ch=getchar();int nn=0,ssss=1;
while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
return nn*ssss;
}
inline bool add(int u,int v){e[++tot].v=v;e[tot].nxt=h[u];h[u]=tot;return true;}
int main(){
// freopen("ex_C.in","r",stdin);
// freopen("C.out","w",stdout);
n=read();m=read();k=read();
for(int i=1;i<=m;i++){int u=read();int v=read();add(u,v);deg[v]++;}
fac[0]=s[0][0]=1;
for(int i=1;i<=k;i++){
fac[i]=Mul(fac[i-1],i);
for(int j=1;j<=i;j++)s[i][j]=vAdd(Mul(s[i-1][j],j),s[i-1][j-1]);
}
f[1][0]=1;int qh=1,qt=1;q[1]=1;
while(qh<=qt){
int np=q[qh++];
for(int i=h[np];i;i=e[i].nxt){
deg[e[i].v]--;if(deg[e[i].v]==0)q[++qt]=e[i].v;
Add(f[e[i].v][0],f[np][0]);
for(int j=1;j<=k;j++)
Add(f[e[i].v][j],vAdd(f[np][j],f[np][j-1]));
}
}
for(int i=1;i<=n;i++){
int ans=0;
for(int j=0;j<=k;j++)Add(ans,Mul(s[k][j],Mul(fac[j],f[i][j])));
cout<