58 lines
1.9 KiB
C++
58 lines
1.9 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
typedef long long LL;
|
||
const int N = 15010, M = 40010;
|
||
int n, m, x[M], num[4][N], cnt[N];
|
||
|
||
// 快读
|
||
LL read() {
|
||
LL x = 0, f = 1;
|
||
char ch = getchar();
|
||
while (ch < '0' || ch > '9') {
|
||
if (ch == '-') f = -1;
|
||
ch = getchar();
|
||
}
|
||
while (ch >= '0' && ch <= '9') {
|
||
x = (x << 3) + (x << 1) + (ch ^ 48);
|
||
ch = getchar();
|
||
}
|
||
return x * f;
|
||
}
|
||
|
||
int main() {
|
||
n = read(), m = read();
|
||
for (int i = 1; i <= m; i++) { // m个魔法值
|
||
x[i] = read();
|
||
cnt[x[i]]++; // 每个魔法值对应的个数
|
||
}
|
||
int sum, A, B, C, D;
|
||
|
||
for (int t = 1; t * 9 + 1 <= n; t++) { // k最小是1，那么9t+1=max(x[D])=n
|
||
sum = 0;
|
||
for (D = 9 * t - 1; D <= n; D++) { // 枚举D
|
||
C = D - t; // 表示C
|
||
B = C - 6 * t - 1; // 根据C推出最大的B
|
||
A = B - 2 * t; // 推出最大的A
|
||
sum += cnt[A] * cnt[B]; // 计算当前A和B的情况
|
||
num[2][C] += cnt[D] * sum; // num[2][C]+=cnt[A]*cnt[B]*cnt[C]
|
||
num[3][D] += cnt[C] * sum; // num[3][D]+=cnt[A]*cnt[B]*cnt[D]
|
||
}
|
||
sum = 0;
|
||
for (A = n - 9 * t - 1; A; A--) { // 倒序枚举A
|
||
B = A + 2 * t;
|
||
C = B + 6 * t + 1; // C的最小值
|
||
D = C + t; // D的最小值
|
||
sum += cnt[C] * cnt[D]; // 计算当前C和D的情况 (涵盖了比C,D大的小所有C',D'的cnt乘积和)
|
||
num[0][A] += cnt[B] * sum; // num[0][A]+=cnt[B]*cnt[C]*cnt[D]
|
||
num[1][B] += cnt[A] * sum; // num[1][B]+=cnt[A]*cnt[C]*cnt[D]
|
||
}
|
||
}
|
||
for (int i = 1; i <= m; i++) {
|
||
for (int j = 0; j < 4; j++)
|
||
printf("%d ", num[j][x[i]]);
|
||
puts("");
|
||
}
|
||
return 0;
|
||
}
|