10.26受虐记
xbx787
·
·
个人记录
今天的联考十分毒瘤。其实是我自己太菜了，啥都没想出来。好吧，看题面：
原题面 提取码: t3ht
我五分钟想出了正解。 ——GJR奆佬
大致题意：有 n 种药剂，有一个可口度 v_i ，还有使用的用量范围 l_i-r_i ，要求必须是两种不同的药剂相配，可口度维两者可口度的乘积。给出 m 个询问，问所有总量为 k 的药剂的可口度之和。
数据：
-
20% : 1<=n,l_i,r_i<=233
-
另外 20% : m=1
-
另外 30% : 1<=l_i,r_i<=2×10^5
-
100% :
1<=n<=5e3 ; 1<=m<=5e5 ; 1<=v_i<=998244352
一开始没有思路，发现 $O(n^4)$ 绝对超时。然后折腾暴力结果爆零。
$Solution$ :
1. 直接暴力即可。（我怎么知道？）
2. 枚举 $i$ , $j$ , $O(1)$ 算即可。（其实是可以拿的）。
3. NTT（反正我不会）
4. 对于每个 $i$ , $j$ , 其贡献如图所示。
可以发现是可以拆成两个区间加等差数列的形式。
那么差分套差分就变成了单点加，最后询问时前缀和变回去即可。
其实看看我的代码会发现这是一个**卡常**题。。。
上代码：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e7+10,mod=998244353;
int n,m,k,b[N];
struct node{int val,l,r;}a[N];
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
inline void chkmax(int &u,int v){if(u<v)u=v;}
signed main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
n=read(),m=read();
for (register int i=1;i<=n;++i)a[i]=(node){read(),read(),read()};
for (register int i=1;i<n;++i)
for (register int j=i+1;j<=n;++j){
int w=(a[i].val*a[j].val)%mod;
(b[a[i].l+a[j].l]+=w)%=mod; (b[a[i].l+a[j].r+1]-=w)%=mod;
(b[a[i].r+a[j].l+1]-=w)%=mod; (b[a[i].r+a[j].r+2]+=w)%=mod;
chkmax(k,a[i].r+a[j].r+2);
}
for (register int i=1;i<=k;++i)(b[i]+=b[i-1])%=mod;
for (register int i=1;i<=k;++i)(b[i]+=b[i-1])%=mod;
for (register int i=1;i<=m;++i)printf("%lld\n",(b[read()]+mod)%mod);
return 0;
}
```
- T2 树上游走
若 $fa[fa[i]]$ 不为零，则在 $i$ 与 $fa[i]$ 间连边。
问从每个点开始随机游走到达根的期望步数（对$998244353$取模）。
数据：
1. 10% : $n=2
-
30% : n=3
-
60% : n<=300
-
100% : 1<=n<=2000,fa[i]<i
1. 2. 人脑计算
3. 高斯消元