JZOJ 6384.珂学家

首先考虑一个不定方程 x1+x2=cx_1+x_2 = c,其中有限制 l1x1r1,l2x2r2l_1 \le x_1 \le r_1,l_2 \le x_2 \le r_2 的整数解的组数。
容易发现确定 x1x_1 并满足 l2cx1r2l_2 \le c - x_1 \le r_2 即可得到一组解。
故共有 min(r1,cl2)max(l1,cr2)+1\min(r_1,c - l_2) - \max(l_1,c - r_2) + 1 组解。

考虑枚举两种试剂 x,yx,y,则对于 c[lx+ly,rx+ry]c \in [l_x + l_y,r_x + r_y]vxvyv_x \cdot v_y 于其的贡献为 min(rx,cly)max(lx,cry)+1\min(r_x,c - l_y) - \max(l_x,c - r_y) + 1
这个不大好处理,但不妨将 cclx+ly,rx+ly,lx+ry,rx+ryl_x + l_y,r_x + l_y,l_x + r_y,r_x + r_y 四个点分类讨论。
不妨设 rx+lylx+ryr_x + l_y \le l_x + r_y,否则可交换。

  1. c[lx+ly,rx+ly)c\in[l_x+l_y,r_x+l_y) 时:
    rx>cly,lx>cryr_x > c-l_y,l_x>c-r_y,故 min(rx,cly)max(lx,cry)+1=lylx+1+c\min(r_x,c - l_y) - \max(l_x,c - r_y) + 1 = - l_y - l_x + 1 + c
    注意到这相当于区间加等差数列,使用二阶差分维护即可。
  2. c[rx+ly,lx+ry)c\in[r_x+l_y,l_x+r_y) 时:
    rxcly,lx>cryr_x\le c-l_y,l_x>c-r_y,故 min(rx,cly)max(lx,cry)+1=rxlx+1\min(r_x,c - l_y) - \max(l_x,c - r_y) + 1 = r_x - l_x + 1
    区间加,维护一阶差分即可,也可以和二阶差分一起维护。
  3. c[lx+ry,rx+ry]c\in[l_x+r_y,r_x+r_y] 时:
    rx<cly,lxcryr_x<c-l_y,l_x\le c-r_y,故 min(rx,cly)max(lx,cry)+1=rx+ry+1c\min(r_x,c - l_y) - \max(l_x,c - r_y) + 1 = r_x + r_y + 1 - c
    同样是等差序列,类似维护即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e3;
const int K = 2e7;
const int mod = 998244353;
int n,m;
int v[N + 5],l[N + 5],r[N + 5];
int s[K + 5];
int main()
{
freopen("a.in","r",stdin),freopen("a.out","w",stdout);
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%d%d%d",v + i,l + i,r + i);
for(register int i = 1;i < n;++i)
for(register int j = i + 1;j <= n;++j)
{
int x,y,w;
w = (long long)v[x = i] * v[y = j] % mod,r[x] + l[y] > l[x] + r[y] && (swap(x,y),1);
s[l[x] + l[y]] = (s[l[x] + l[y]] + w) % mod,s[r[x] + l[y] + 1] = (s[r[x] + l[y] + 1] - w + mod) % mod,s[l[x] + r[y] + 1] = (s[l[x] + r[y] + 1] - w + mod) % mod,s[r[x] + r[y] + 2] = (s[r[x] + r[y] + 2] + w) % mod;
}
for(register int i = 1;i <= K;++i)
s[i] = (s[i] + s[i - 1]) % mod;
for(register int i = 1;i <= K;++i)
s[i] = (s[i] + s[i - 1]) % mod;
int k;
for(;m;--m)
scanf("%d",&k),printf("%d\n",s[k]);
}