本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-23 09:30:29

记录

A 题仿照 QOJ8336 写了个二分，但是由于 $inf$ 精度爆了，同时有超过一半的数据包含 $n=10^{18}$，挂到 $44$。

B 题构造了一个多小时，但是忘记特判 $k=1$，同时有超过一半的数据包含 $k=1$ 且 $\frac nk$ 为奇数，挂到 $38$。

C 题想了主席树 + 二分的做法，还胡出来一个奇怪的矩形求和做法，最后都感觉很难写弃了，写了一个前缀和上二分，但是由于二分上界的 $k$ 写成了 $q$，从 $30$ 挂到 $3$。

D 题没太认真想，直接写了 $40$ 的暴力，最后过了 $53$。（事实上赛后自己认真做想出的做法是假的，只能过 $36$）

所以比赛时边界和特判这种细节需要注意，避免挂分。/ll

题解

A. T386386 谜之阶乘

发现 $20$ 的阶乘已经超过了 $10^{18}$，所以答案的长度不会超过 $20$。考虑枚举答案长度，显然在长度相同的前提下，开头越大，最终的乘积就越大。所以可以二分求出第一个不小于 $n$ 的开头位置，再判断一下是否与 $n$ 相等即可。

另外要防止溢出爆掉，只需要在乘法计算前用 __int128 判断一下，如果超过边界就返回边界即可。时间复杂度大概是 $O(400\log VT)$，但是由于暴力计算乘法会在爆掉时退出，极大地跑不满，可以通过。

#include<iostream>
#define int long long 
#define pii pair<int,int>
#define ll __int128
using namespace std;
const int P=2e18;
int n,ct;
pii ans[30];
bool check(int x,int y)
{
	ll te=x;
	te*=y;
	if(te>P) return true;
	return false;
}
int query(int l,int len)
{
	int res=1;
	for(int i=0;i<len;i++)
	{
		if(check(res,l+i)) return P;
		res*=(l+i);
	}
	return res;
}
void sol()
{
	cin>>n,ct=0;
	if(n==1) {cout<<-1<<'\n'; return;}
	for(int i=20;i>=2;i--)
	{
		int l=1,r=P,res=-1;
		while(l<=r)
		{
			int mid=(l+r)\/2;
			if(query(mid,i)<=n) res=mid,l=mid+1;
			else r=mid-1;
		}
		if(res!=-1&&res!=1&&query(res,i)==n) ans[++ct]={res+i-1,res-1};
	}
	ans[++ct]={n,n-1},cout<<ct<<'\n';
	for(int i=1;i<=ct;i++) cout<<ans[i].first<<' '<<ans[i].second<<'\n';
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int TT; cin>>TT;
	while(TT--) sol();
	return 0;
}

B. T386254 子集

发现可以按照 $k$ 个一组划分成 $m=\frac nk$ 组，每组内等价于一个 $1$ 到 $k$ 的排列，只要把 $m$ 组排列分别分到 $k$ 个组里，使得每个组内的和相等即可。

不难注意到 $m$ 为偶数时只需要正序逆序交替即可，下面讨论 $m$ 为奇数的情况。此时若 $k$ 为偶数，我觉得无解，不会证。

$k$ 为奇数时先从 $m$ 个排列中取出三个，第一个从 $1$ 到 $k$，第二个从第 $(\frac{k+1}2+1)$ 组开始从 $1$ 到 $k$，可以发现这样能保证所有组中的和恰好好是一个公差为 $1$ 的等差数列。那么用第三个数补充上就恰为一个排列，之后就转化为 $m$ 为偶数的情况了，不太懂是怎么构造出来的，我是打表 + 枚举找到的。

#include<iostream>
#include<vector> 
#define int long long 
using namespace std;
const int N=1e6+10;
int n,k,m,cnt;
vector <int> res[N];
void sol()
{
	cin>>n>>k,m=n\/k,cnt=0;
	if(k==1) 
	{
		cout<<"Yes\n";
		for(int i=1;i<=n;i++) cout<<i<<' ';
		return;
	}
	for(int i=1;i<=k;i++) res[i].clear();
	if(m==1) {cout<<"No\n"; return;}
	if(m%2)
	{
		if(k%2==0) {cout<<"No\n"; return;}
		for(int i=1;i<=k;i++) cnt++,res[i].push_back(cnt);
		for(int i=0;i<k;i++) cnt++,res[((k+1)\/2+1+i-1)%k+1].push_back(cnt);
		int sum=((k+1)\/2+k)*3;
		for(int i=1;i<=k;i++) res[i].push_back(sum-res[i][0]-res[i][1]);
		m-=3,cnt+=k;
	}
	cout<<"Yes\n";
	for(int i=1;i<=m;i++) 
	{
		if(i%2) for(int j=1;j<=k;j++) cnt++,res[j].push_back(cnt);
		else for(int j=k;j>=1;j--) cnt++,res[j].push_back(cnt);
	}
	for(int i=1;i<=k;i++)
	{
		for(int t:res[i]) cout<<t<<' ';
		cout<<'\n';
	}
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int TT; cin>>TT;
	while(TT--) sol();
	return 0;
}

C. T386330 粉末

发现每个询问本质上是询问 $x$ 位置上的块数第一次到达 $y$ 的操作数，显然可以二分，那么就需要快速求出操作若干次后某个位置上的块数。

同时发现已经落下的方块不会改变，那么可以把所有询问离线下来，在所有操作结束后询问。若答案序号大于询问的序号，说明这个位置是在询问之后才被填上的，在询问时是空气。这样就把所有询问离线下来了。

考虑从小到大枚举所有的 $x$，并维护长为 $q$ 的序列 $s$ 使得 $s_i$ 表示前 $i$ 个操作中给 $x$ 处加的块数。那么对于第 $k$ 个增加操作 $s_k=(l_i,r_i,h_i)$，在枚举到 $l_i$ 时在 $s$ 的 $[k,q]$ 上加 $h_i$，枚举到 $r_i+1$ 时在 $s$ 的 $[k,q]$ 上减 $h_i$，就可以保证这次操作只会影响到 $x\in[l_i,r_i]$。

那么就需要支持区间修改（事实上是后缀修改），可以使用线段树 / 树状数组上二分，也可以在二分中用数据结构单点查询。下面的代码是二分 + 树状数组查询，时间复杂度是 $O(q\log^2 q)$ 的。

代码

#include<iostream>
#include<vector>
#define int long long 
#define pii pair<int,int>
using namespace std;
const int N=1e6+10;
int n,q,res[N];
vector <pii> opt[N],ask[N];
struct bit
{
	int b[N];
	int lowbit(int x) {return x&(-x);}
	void add(int p,int x) {for(;p<=q;p+=lowbit(p)) b[p]+=x;}
	int query(int p) {int tr=0; for(;p;p-=lowbit(p)) tr+=b[p]; return tr;}
}T;
int check(int x)
{
	int l=1,r=q,pos=0;
	while(l<=r)
	{
		int mid=(l+r)\/2;
		if(T.query(mid)>=x) pos=mid,r=mid-1;
		else l=mid+1;
	}
	return pos;
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int k=1;k<=q;k++)
	{
		int op; cin>>op,res[k]=-1;
		if(op==1)
		{
			int l,r,h; cin>>l>>r>>h;
			opt[l].push_back({k,h}),opt[r+1].push_back({k,-h});
		}
		else
		{
			int x,y; cin>>x>>y;
			ask[x].push_back({y,k});
		}
	}
	for(int i=1;i<=n;i++) 
	{
		for(pii te:opt[i]) T.add(te.first,te.second);
		for(pii te:ask[i]) res[te.second]=check(te.first);
	}
	for(int i=1;i<=q;i++) if(res[i]!=-1) cout<<(res[i]>i?0:res[i])<<'\n';
	return 0;
}

D. T386391 排水系统

考虑每条边断掉时的影响，发现边 $(u,v)$ 断掉时其他边一定还存在，所以流入 $u$ 点的水量与没有边断掉时的水量相等。这时只需要处理从点 $u$ 流出去的点接收到的水量即可。

这里设 $s_u$ 表示从 $u$ 点连出去的出边数量，$d_u$ 表示没有边被断掉时流入 $u$ 点的水量，可以先跑一遍拓扑排序预处理出来。

那么边被断掉之前每个从 $u$ 连出去的点都会接收到 $\frac{d_u}{s_u}$ 的水，断掉之后除 $v$ 点外每个点会收到 $\frac{d_u}{s_u-1}$ 的水，增加了 $\frac{d_u}{s_u-1}-\frac{d_u}{s_u}$；$v$ 点不会从 $u$ 点接受到水。

如果暴力修改这些东西，复杂度可以被卡到 $O(k^2)$，不可接受。我们发现只有 $v$ 一个点不同，那么考虑把其他点变多的水量乘上 $s_u$ 放到 $u$ 点上，化简得 $t=s_u(\frac{d_u}{s_u-1}-\frac{d_u}{s_u})=\frac{d_u}{s_u-1}$。这时流向每个点的水量都变成了 $\frac {d_u}{s_u-1}$，那么单独给 $v$ 点减去 $\frac{d_u}{s_u-1}=t$ 消去就行。（这里 $u$ 增加和 $v$ 减少的量相等也保证了水量不变）

需要注意对 $u,v$ 两点的操作建立在边 $(u,v)$ 断掉的基础上，所以这些修改均需要乘上边断掉的概率 $p_j$，也就是说给 $u$ 点加上 $tp_j$，给 $v$ 点加上 $-tp_j$。

把每一条边的贡献累加完后，就相当于把所有情况的变化量带权地放到了节点上。这时再正常给初始节点分别放入 $1$ 的水，跑一遍拓扑排序就得到答案了。时间复杂度 $O(n+k)$。（注意两次拓扑的数组别用混，我因为这个调了好久）

代码

#include<iostream>
#include<queue>
#define int long long 
using namespace std;
const int N=1e6+10;
const int mod=998244353;
int po(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod,b>>=1; 
	}
	return res;
}
int n,m,R,k,tot,itot,ans[N],res[N],r[N],s[N],tr[N],d[N];
int to[N],a[N],nxt[N],head[N],st[N];
bool f[N]; 
queue <int> q;
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>R>>k;
	for(int i=1;i<=k;i++)
	{
		cin>>st[i]>>to[i]>>a[i],tot+=a[i]; 
		r[to[i]]++,s[st[i]]++,nxt[i]=head[st[i]],head[st[i]]=i;
	}
	itot=po(tot%mod,mod-2);
	for(int i=1;i<=n;i++) 
	{
		tr[i]=r[i];
		if(!r[i]) d[i]=1,q.push(i);
		else d[i]=0;
	}
	while(q.size())
	{
		int u=q.front(); q.pop();
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			d[v]=(d[v]+d[u]*po(s[u],mod-2)%mod)%mod,r[v]--;
			if(!r[v]) q.push(v);
		}
	}
	for(int i=1;i<=k;i++)
	{
		int v=to[i],u=st[i],ts=d[u]*po(s[u]-1,mod-2)%mod*a[i]%mod*itot%mod;
		res[u]=(res[u]+ts)%mod,res[v]=(res[v]-ts+mod)%mod;
	}
	for(int i=1;i<=n;i++) 
	{
		r[i]=tr[i];
		if(!r[i]) res[i]++,q.push(i);
	}
	while(q.size())
	{
		int u=q.front(); q.pop();
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			res[v]=(res[v]+res[u]*po(s[u],mod-2)%mod)%mod,r[v]--;
			if(!r[v]) q.push(v);
		}
	}
	for(int i=n-R+1;i<=n;i++) cout<<res[i]<<' ';
	return 0;
}