JZOJ 6384 珂学家

发表于 | 分类于 |

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

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

  1. 当 \(c\in[l_x+l_y,r_x+l_y)\) 时：
    \(r_x > c-l_y,l_x>c-r_y\)，故 \(\min(r_x,c - l_y) - \max(l_x,c - r_y) + 1 = - l_y - l_x + 1 + c\)。
    注意到这相当于区间加等差数列，使用二阶差分维护即可。
  2. 当 \(c\in[r_x+l_y,l_x+r_y)\) 时：
    \(r_x\le c-l_y,l_x>c-r_y\)，故 \(\min(r_x,c - l_y) - \max(l_x,c - r_y) + 1 = r_x - l_x + 1\)。
    区间加，维护一阶差分即可，也可以和二阶差分一起维护。
  3. 当 \(c\in[l_x+r_y,r_x+r_y]\) 时：
    \(r_x<c-l_y,l_x\le c-r_y\)，故 \(\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]);
}