整套都是原题所以就不设密码了（
原题页面：https://ac.nowcoder.com/acm/contest/65193
题解：https://www.nowcoder.com/discuss/540225827162583040
\(60+30+20+20=130\)。
每日挂分之T2线段树不开\(4\)倍+\(10^6\)数量级输入不关同步流，\(\bf\colorbox{MidnightBlue}{\texttt{\color{White}{TLE}}}\ \ 100\to 30\)。
A
赛时光想着\(f[i][j]\)表示\(i\)个元素选\(j\)个的答案，磕了半天没想出来。
实际上这道题应该从值域为\(n\)这一特征入手，这子集之和最大是\(\frac{n(n+1)}{2}\)。
因此我们考虑枚举子集之和\(x\)，用dp求出有多少种选法能达到这个子集和\(y\)。答案即为所有\(x^y\)相乘，用快速幂优化一下。
但是\(y\)可能非常大，但它作为指数不能直接取模。我们可以利用欧拉定理（其实就是费马小定理的推广）\(a^{\varphi(m)}\equiv1\pmod n\)，将指数对\(\varphi(998244353)=998244352\)取模即可。
时间复杂度\(O(n^3)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 202
#define mod 998244353
using namespace std;
int n,f[N][N*N]={1},ans=1;
int qp(int a,int b){
int koishi=1;
while(b){
if(b&1) koishi=koishi*a%mod;
a=a*a%mod,b>>=1;
}
return koishi;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=0;j<=n*(n+1)/2;j++){
f[i][j]=f[i-1][j];
if(j>=i) f[i][j]=(f[i][j]+f[i-1][j-i])%(mod-1);
}
}
for(int i=1;i<=n*(n+1)/2;i++) ans=ans*qp(i,f[n][i])%mod;
cout<<ans<<"\n";
return 0;
}
B
原题：P3488 [POI2009] LYZ-Ice Skates
我？赛时切紫？真的假的？！
假的 因为这个或那个的原因传奇地挂了\(70\)分，本来是可以切的。。。学到的：用cin一定要关同步流，线段树开\(4\)倍。
我们把每个住户选择的范围\([l,r]\)看作线段。
有解\(\iff\)对于所有区间，都有\(\bf x\le len\times k\)。其中\(\bf len\)是该区间的长度，\(\bf x\)是该区间覆盖的线段数。
- 充分性：\(len\times k\)就是这个区间内的房间数量，所以如果该区间内的住户数量\(>\)房间数量，那么房间是不够用的。
- 必要性：显然，无解\(\iff\)存在长度为\(d+1\)的区间不合法，那么有解\(\iff\)所有长度为\(d+1\)的区间都合法。
在有解时考虑最极端的情况，即最大化\(x\)。显然此时需要\(d=0\)，且所有长度为\(d+1\)的区间都放满了\(k\)条线段，那么总共覆盖的线段数量\(x=(len-d)\times k=len\times k\)。在有解的情况下\(x\)最大取到\(len\times k\)，所以\(x\le len\times k\Rightarrow\)有解。
于是我们只需要判断该结论是否成立即可。
由于区间等长，我们简化一下，只统计区间左端点，判断是否存在区间\([l,r]\)使得\(x\le (len+d)\times k\)，其中\(len=r-l+1\)，\(x\)是\([l,r]\)覆盖的左端点个数。
这样还是不太容易看，我们移一下项：\(x-len\times k\le d\times k\)。
其中\(d\times k\)是常数，所以我们把\((x-len\times k)\)看作一个整体扔进线段树维护即可。这种把位置相关量和值看作一个整体来维护的技巧之前洛谷比赛有过：P11157 【MX-X6-T3】さよならワンダーランド ~ 题解。
更具体地，由于只要存在\((x-len\times k)>d\times k\)就是不合法的。所以我们需要想办法维护出那个\((x-len\times k)\)最大的区间来与\(d\times k\)进行比较。所以我们用线段树来维护一个最大连续子段和，模板题 P4513 小白逛公园，转移并不难理解，可以去看下洛谷的题解。
这样求出最大连续子段和，判定答案并输出即可。时间复杂度\(O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
#define int long long
#define N 500010
using namespace std;
int n,m,k,d,sum[N<<2],maxx[N<<2],lmax[N<<2],rmax[N<<2];
void update(int x){
sum[x]=sum[lc(x)]+sum[rc(x)];
maxx[x]=max({maxx[lc(x)],maxx[rc(x)],rmax[lc(x)]+lmax[rc(x)]});
lmax[x]=max({lmax[lc(x)],sum[lc(x)]+lmax[rc(x)]});
rmax[x]=max({rmax[rc(x)],sum[rc(x)]+rmax[lc(x)]});
}
void build(int x,int l,int r){
if(l==r){
sum[x]=-k;
return;
}
int mid=(l+r)>>1;
build(lc(x),l,mid),build(rc(x),mid+1,r);
update(x);
}
void chp(int a,int v,int x,int l,int r){
if(l==r){
sum[x]+=v;
lmax[x]=rmax[x]=maxx[x]=max(0ll,sum[x]);
return;
}
int mid=(l+r)>>1;
if(a<=mid) chp(a,v,lc(x),l,mid);
else chp(a,v,rc(x),mid+1,r);
update(x);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>k>>d;
build(1,1,n-d);
int x,y;
while(m--){
cin>>x>>y;
chp(x,y,1,1,n-d);
if(maxx[1]>d*k) cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}