czm's Blog

this.log();

0%

包装纸问题 题解

发表于 更新于 分类于

作者：czm23333

题目传送门

题目大意

给定一个m列n行的网格，给定每行列的宽度，求：

  1. 其中网格矩形的数量
  2. 所有网格矩形的面积和

由于$n, m$同级，以下计算的时间复杂度内均把$n, m$合并

Subtask 0

枚举每个矩形计算即可，时间复杂度$\Theta (n^4)$

Subtask 1

here

Method #2

时间复杂度$\Theta (n^2)$

Subtask 2

其实在上面的文章的最后一部分有提到正解做法，不过当时并没有仔细想，只是口胡了一下，实际上里面有一些错误。

在这里再写一下正解做法：

$N$的算法已经在上面文章里写出，下面只讲$S$算法。

考虑矩形的一条边，一定是在相应网格轴上由若干条连续线段组成的，而且确定两条边一定能唯一地确定一个矩形。

大家都学过矩形面积等于长乘宽，不过这里我们要统计所有矩形的面积和，怎么统计呢？自然是每种可能的长乘宽都加起来。

但是这样就变回Subtask 0的$\Theta (n^4)$算法了，必须优化。

回忆一下多项式乘法，两个多项式相乘就等于每两项都相乘一次再加起来。实数乘法也没差，多个实数的和与另外一些实数的和相乘就等于每两个数都相乘一次再加起来。

那么我们就可以枚举每一种长，加起来；再枚举每一种宽，加起来；最后把两个和相乘，就得到了答案。

但是这样还是$\Theta (n^2)$的，过不了，我们要加速两个求和的过程。

对于每次求和，我们不再枚举每种可能的长度，而是枚举每一条线段，计算它对整个和的贡献。显然一条线段对和的贡献等于它的长度乘被包含在不同连续线段里的次数。

这个次数怎么计算呢？

显然计算长和宽的方法是相同的，所以接下来我们不再区分长和宽。

我们先考虑有偶数条线段的情况，很明显，贡献次数有对称性，也就是这时候我们只要算半边就行了，另外半边对称过来就好。

当我们计算从左往右数第$i$条线段$(i \leq \frac n2)$时，稍微观察一下可以得到：

对于包含$l$条线段的所有连续线段：

如果$1 \leq l \leq i$，则有$l$条这样的线段会包含第$i$条线段

如果$i < l \leq n - i$，则有$i$条这样的线段会包含第$i$条线段

如果$n - i < l$，则有$n - l + 1$条这样的线段会包含第$i$条线段

写出来就是形如$1, 2, 3, 4, 4, 4, 4, 3, 2, 1$这样的形状，可以发现就是俩等差数列加中间定值一段，可以$\Theta (1)$求和。于是对于每条线段都这样求一次，就能$\Theta (n)$解决问题。

当有奇数条线段，实际上大部分地方还是没什么区别，可以像偶数条那样算，但是整个序列的中间多出了一个既不在左半边，又不在右半边的玩意儿，所以我们要额外考虑一下这个。

可以很容易地看出：

对于包含$l$条线段的所有连续线段：

如果$1 \leq l \leq i$，则有$l$条这样的线段会包含第$i$条线段

如果$i < l \leq n$，则有$n - l + 1$条这样的线段会包含第$i$条线段

写出来就是形如$1, 2, 3, 4, 3, 2, 1$这样的形状，可以发现就是俩等差数列，也可以$\Theta (1)$求和。

对于上面复杂的结论，我们再一通化简就可以得到，第$i$条线段的贡献次数就等于$i(n-i+1)$。

于是我们$\Theta (n)$解决了整个问题。

然后空间显然可以做到$\Theta (1)$，你可以一边输入一边计算和，最后输出相乘结果即可。

STD（本题输入量较大，因此要带上快读，快读板子来自oi-wiki）：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream>
using namespace std;

#define DEBUG 0
struct IO {
#define MAXSIZE (1 << 10)
#define MAXPSIZE (1 << 5)
#define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], * p1, * p2;
    char pbuf[MAXPSIZE], * pp;
#if DEBUG
#else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
    inline char gc() {
#if DEBUG  // 调试，可显示字符
        return getchar();
#endif
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
        return p1 == p2 ? ' ' : *p1++;
    }
    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }
    template <class T>
        requires std::is_signed_v<T>
    inline void read(T& x) {
        double tmp = 1;
        bool sign = 0;
        x = 0;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
        if (ch == '.')
            for (ch = gc(); isdigit(ch); ch = gc())
                tmp /= 10.0, x += tmp * (ch - '0');
        if (sign) x = -x;
    }
    template <class T>
        requires std::is_unsigned_v<T>
    inline void read(T& x) {
        double tmp = 1;
        x = 0;
        char ch = gc();
        for (; !isdigit(ch); ch = gc());
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
        if (ch == '.')
            for (ch = gc(); isdigit(ch); ch = gc())
                tmp /= 10.0, x += tmp * (ch - '0');
    }
    inline void read(char* s) {
        char ch = gc();
        for (; blank(ch); ch = gc())
            ;
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
    }
    inline void read(char& c) {
        for (c = gc(); blank(c); c = gc())
            ;
    }
    inline void push(const char& c) {
#if DEBUG  // 调试，可显示字符
        putchar(c);
#else
        if (pp - pbuf == MAXPSIZE) fwrite(pbuf, 1, MAXPSIZE, stdout), pp = pbuf;
        *pp++ = c;
#endif
    }
    template <class T>
        requires std::signed_integral<T>
    inline void write(T x) {
        if (x < 0) x = -x, push('-');  // 负数输出
        static T sta[35];
        T top = 0;
        do {
            sta[top++] = x % 10, x /= 10;
        } while (x);
        while (top) push(sta[--top] + '0');
    }
    template <class T>
        requires std::unsigned_integral<T>
    inline void write(T x) {
        static T sta[35];
        T top = 0;
        do {
            sta[top++] = x % 10, x /= 10;
        } while (x);
        while (top) push(sta[--top] + '0');
    }
    template <class T>
    inline void write(T x, char lastChar) {
        write(x), push(lastChar);
    }
    inline void write(const char* str) {
        while (*str != '\0') {
            push(*str);
            ++str;
        }
    }
} io;

constexpr unsigned long long P = 1000000007ull;
constexpr unsigned long long inv4 = 250000002ull;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	unsigned long long c[2];
	io.read(c[0]); io.read(c[1]);
	unsigned long long s[2] = { 0 };
	for (unsigned id = 0; id <= 1; ++id)
		for (unsigned long long i = 1; i <= c[id]; ++i) {
			unsigned long long tmp;
			io.read(tmp);
			s[id] += i * (c[id] - i + 1) % P * tmp % P;
			s[id] %= P;
		}
	io.write(c[0] * c[1] % P * (c[0] + 1) % P * (c[1] + 1) % P * inv4 % P, ' '); io.write(s[0] * s[1] % P);

	return 0;
}