杂题乱记

本页所有动态规划内容已迁移至 动态规划 刷题记录。

P8186 [USACO22FEB] Redistributing Gifts S

Problem Link

有一群人收到了礼物，每个人都有对每个礼物的喜爱度列表。他们商量后决定重新分配礼物，每个人都希望可以拿到他更喜爱的礼物，至少不能差于他原来的礼物。现在需要找到每个人重新分配后，他可以拿到的最喜欢的礼物是哪一个。所有人的答案可以不是同一轮中的。

tag: Floyd, 传递闭包

Solution

可以发现礼物的分配是由交换产生的，所以从自身向他希望得到的所有礼物连一条边。由于一开始礼物的编号和人的编号一一对应，所以连边等价于连他可以和谁交换。如果多个人 ($\geq 2$) 处于同一个环，那么说明这样交换是成立的。

如下面的数据：

5 4 3 2 1
1 2 5 4 3
2 3 4 1 5
5 1 4 2 3
4 5 2 1 3

可以建出如下的图：

其中 1 2 3 与 1 5 4 均成环，有两种方案。

在图中，可以通过 Floyd 传递闭包判环，设 $f_{i,j}$ 为 $i\to j$ 是否有边，特别的，$f_{i,i}=1$。那么可以轻易写出转移方程 $f_{i,j}=f_{i,j}\ \text{or}\ (f_{i,k}\ \text{and}\ f_{k,j})$，考虑 bitset 优化。

传递闭包部分代码：

bitset<N> f[N];
for(int k=1;k<=3;k++) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(f[i][j]) f[i]|=f[j];
        }
    }
}

循环 $3$ 次避免顺序问题。

若 $f_{u,v}=f_{v,u}=\text{true}$，则说明 $u, v$ 在一个环上。

Core Code

bitset<N> f[N];
int main() {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(a[i][j-1]==i) break;
            f[i][a[i][j]]=1;
        }
    }
    for(int k=1;k<=3;k++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                if(f[i][j]) f[i]|=f[j];
            }
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(f[i][a[i][j]] && f[a[i][j]][i]) {
                printf("%d\n",a[i][j]);
                break;
            }
        }
    }
    return 0;
}

P1485 火枪打怪

Link

有 $n$ 只怪物排成一排，每只怪物的血量为 $m_i$。有 $k$ 发子弹，每发子弹的威力为 $p$。射击第 $i$ 只怪物时，除了这个怪物受到 $p$ 点伤害，它左边的怪物也可能受到溅射伤害，溅射伤害为 $\max(0, p - (i - j)^2)$，求最小的 $p$。

tag: 二分答案, 前缀和

Solution

考虑二分答案。

• 注意到操作右边要比操作左边优，check 时从后往前循环。

• 设当前位置为 $j$，操作 $i$ 时能对 $j$ 产生影响当且仅当 $i-j<\sqrt{p}$。也就是说，只需要考虑 $[j+1, j+\sqrt{p}]$ 区间操作的影响，这样的时间复杂度为 $\mathcal{O}(n^2)$。

• 考虑优化，设区间内共操作了 $sum$ 次，每次操作的位置为 $r_i(1\leq i\leq sum)$。那么对于 $j$ 受到的伤害，满足下面的式子

  $$\begin{aligned} &\sum_{i=1}^{sum}[p-(r_i, j)^2]\\ =&sum\times p-\sum_{i=1}^{sum}r_i^2+2j\times \sum_{i=1}^{sum}r_i-sum\times j^2 \end{aligned}$$

• 这样的复杂度仍为 $\mathcal{O}(n^2)$，考虑预处理其中的变量。首先 $sum$ 可以用后缀和优化（$sum^{\prime}_j$ 表示使 $j\sim n$ 血量清零需要的操作数）。观察到 $r_j$ 和 $r_j^2$ 都需要求和，仍然考虑后缀和优化，令 $r^{\prime}_j$ 表示 $j\sim n$ 所有操作位置的和，$r^{\prime 2}_j$ 同理。优化为 $\mathcal{O}(n)$。

Core Code

bool check(int p) {
    int maxd = sqrt(p);
    for (int i = 1; i <= n; i++) {
        hp[i] = m[i]; 
    }
    for (int j = n; j >= 1; j--) {
        sum[j] = sum[j + 1];
        ri2[j] = ri2[j + 1];
        ri[j] = ri[j + 1];
        int nowsum = sum[j] - sum[j + maxd + 1];
        hp[j] -= nowsum * p
               - (ri2[j] - ri2[j + maxd + 1])
               + 2 * j * (ri[j] - ri[j + maxd + 1])
               - nowsum * j * j;
        while (hp[j] >= 0) {
            hp[j] -= p;
            sum[j]++;
            ri2[j] += j * j;
            ri[j] += j;
            if (sum[j] > k) return 0;
        }
    }
    return 1;
}

P6600 「EZEC-2」字母

Link

在 $0/1$ 矩阵中，找到有多少个满足下面要求的横长 $w$ 竖长 $h$ 的 T 字形

• $w\geq a$
• $h\geq b$
• $w\times h\geq s$
• $w+h\geq x$

tag: 二维前缀和

Solution

一眼非常像 NOIP2022 T1。

首先想如何 brute，先枚举矩阵中每个为 $1$ 的点作为 T 的中心点，用前缀和记录它的左、右、下各有多少个 $1$，不妨分别设为 $suml, sumr, sumd$。然后暴力判断这些 $1$ 能组成多少个中心点重叠的符合条件的 T。

考虑优化掉判断符合条件部分的算法，暴力枚举横长竖长，$f_{w, h}$ 表示横长 $w$ 竖长 $h$ 的 T 字形是否满足条件。时间复杂度 $\mathcal{O}(n^2)$。

计算答案时，对于每个位置 $(i,j)$，枚举它可能的横长竖长，显然对于这个位置 $w_{max} = \min\{suml_{i, j}, sumr_{i, j}\}\times 2 - 1,\ h_{max} = sumd_{i, j}$。即 $ans_{i, j} = \sum_{w = 3}^{w_{max}}\sum_{h = 2}^{h_{max}} f_{w, h}$，时间复杂度过高。

继续优化掉这一部分，注意到是统计区间和，想到二维前缀和，用 $sum_{i, j}$ 表示 $\sum_{w = 3}^{i}\sum_{h = 2}^{j} f_{w, h}$。简单容斥一下得到 $sum_{i, j} = sum_{i - 1, j} + sum_{i, j - 1} + f_{i, j} - sum_{i - 1, j - 1}$。

这样总体复杂度 $\mathcal{O}(n^2)$。

Core Code

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (in[i][j] == '0') suml[i][j] = 0;
        else suml[i][j] = suml[i][j - 1] + 1;
    }
    for (int j = m; j >= 1; j--) {
        if (in[i][j] == '0') sumr[i][j] = 0;
        else sumr[i][j] = sumr[i][j + 1] + 1;
    }
}
for (int j = 1; j <= m; j++) {
    for (int i = n; i >= 1; i--) {
        if (in[i][j] == '0') sumd[i][j] = 0;
        else sumd[i][j] = sumd[i + 1][j] + 1;
    }
}
for (int w = 3; w <= m; w++) {
    for (int h = 2; h <= n; h++) {
        if ((w & 1) && w >= a && h >= b && w * h >= s && w + h >= x) {
            f[w][h] = 1;
        }
        sum[w][h] = sum[w - 1][h] + sum[w][h - 1] + f[w][h] - sum[w - 1][h - 1];
    }
}
int ans = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        int w = min(suml[i][j], sumr[i][j]) * 2 - 1;
        int h = sumd[i][j];
        if (in[i][j] == '1') ans += sum[w][h];
    }
}
cout << ans << endl;

P7915 [CSP-S 2021] 回文

Link

给定一个整数序列 $a_1, a_2,\dots, a_{2n}$，保证包含 $1\sim n$ 的数各两次。可以在 $a$ 序列的首或尾选择一个数 push_back 到 $b$ 序列中并删除 $a$ 中的这个数，使得 $b$ 为一个回文串。每次操作记为 L 或 R，表示从开头或结尾选择元素，输出操作串字典序最小的方案。

tag: 双端队列

Solution

以下以第一步取 $a_1$ 为例，取 $a_{2n}$ 同理。

由于要构成回文串，对于有且仅有的一个 $k$ 使得 $a_1=a_k$，$a_k$ 一定最后取到。

所以题目可以转化为，对于 $a_2\dots a_{k-1}$，从前向后取元素，而对于 $a_{k+1}\dots a_{2n}$，从后向前取元素。

即可以把这两部分看作一个栈，从第二次操作开始，每次从栈顶取元素，那么应该从哪边取呢？

可以从最后的操作开始分析，倒数第二次操作只能取 $a_{k-1}$ 或 $a_{k+1}$，由于要构成回文串，就需要满足栈顶等于 $a_k$ 两侧的元素。那么想到可以将两侧转化为双端队列，每次满足有其中一个队列的队首等于任意一个的队尾，如下图

一个 string 需要注意的点，每次 s = "L" + s 的复杂度是 $\mathcal{O}(n)$ 的，可以通过 s.push_back("L") 最后 reverse(s.begin(), s.end()) 来解决。

Core Code

bool check_l() {
    int k;
    ans = "L";
    revans = "L";
    for (int i = 2; i <= n; i++) {
        if (a[i] == a[1]) {
            k = i;
            break;
        }
    }
    deque<int> st1, st2;
    for (int i = 2; i < k; i++) st1.push_back(a[i]);
    for (int i = k + 1; i <= n; i++) st2.push_front(a[i]);
    while (!st1.empty() || !st2.empty()) {
        if (st1.size() > 1 && st1.front() == st1.back()) {
            ans.push_back('L');
            revans.push_back('L');
            st1.pop_front(); st1.pop_back();
        } else if (st1.size() && st2.size() && st1.front() == st2.back()) {
            ans.push_back('L');
            revans.push_back('R');
            st1.pop_front(); st2.pop_back();
        } else if (st1.size() && st2.size() && st2.front() == st1.back()) {
            ans.push_back('R');
            revans.push_back('L');
            st2.pop_front(); st1.pop_back();
        } else if (st2.size() > 1 && st2.front() == st2.back()) {
            ans.push_back('R');
            revans.push_back('R');
            st2.pop_front(); st2.pop_back(); 
        } else {
            return 0;
        }
    }
    return 1;
}
bool check_r() {
    int k;
    ans = "R";
    revans = "L";
    for (int i = 1; i < n; i++) {
        if (a[i] == a[n]) {
            k = i;
            break;
        }
    }
    deque<int> st1, st2;
    for (int i = 1; i < k; i++) st1.push_back(a[i]);
    for (int i = k + 1; i < n; i++) st2.push_front(a[i]);
    while (!st1.empty() || !st2.empty()) {
        if (st1.size() > 1 && st1.front() == st1.back()) {
            ans.push_back('L');
            revans.push_back('L');
            st1.pop_front(); st1.pop_back();
        } else if (st1.size() && st2.size() && st1.front() == st2.back()) {
            ans.push_back('L');
            revans.push_back('R');
            st1.pop_front(); st2.pop_back();
        } else if (st1.size() && st2.size() && st2.front() == st1.back()) {
            ans.push_back('R');
            revans.push_back('L');
            st2.pop_front(); st1.pop_back();
        } else if (st2.size() > 1 && st2.front() == st2.back()) {
            ans.push_back('R');
            revans.push_back('R');
            st2.pop_front(); st2.pop_back(); 
        } else {
            return 0;
        }
    }
    return 1;
}
int main() {
    T = read();
    while (T--) {
        n = read() * 2;
        for (int i = 1; i <= n; i++) {
            a[i] = read();
        }
        if (check_l()) {
            reverse(revans.begin(), revans.end());
            cout << ans + revans << endl;
        } else if (check_r()) {
            reverse(revans.begin(), revans.end());
            cout << ans + revans << endl;
        }
        else {
            cout << -1 << endl;
        }
    }
    return 0;
}

P1053 [NOIP2005 提高组] 篝火晚会

Link

▶

题意

佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有 $n(3\le n \le 50000)$ 个同学，编号从 $1$ 到 $n$。一开始，同学们按照 $1,2,\cdots ,n$ 的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。

佳佳可向同学们下达命令，每一个命令的形式如下：

$$(b_1, b_2,... b_{m-1}, b_m)$$

这里 $m$ 的值是由佳佳决定的，每次命令 $m$ 的值都可以不同。这个命令的作用是移动编号是 $b_1,b_2,\cdots, b_m$ 的这 $m$ 个同学的位置。要求 $b_1$ 换到 $b_2$ 的位置上，$b_2$ 换到 $b_3$ 的位置上，……，要求 $b_m$ 换到 $b_1$ 的位置上。执行每个命令都需要一些代价。我们假定如果一个命令要移动 $m$ 个人的位置，那么这个命令的代价就是 $m$。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？

选择的 $m$ 个人不必连续。

tag: 环

Solution

发现如果有 $k$ 个人在初始环和目标环中位置相等，那么剩下的人只需要移动 $n-k$ 次即可，因为他们的移动一定可以组成环。

但是建出来的环不一定能使 $k$ 取到最大值，所以可以通过类似转一下的方式。

初始环	1	2	3	4	5	6
目标环	2	3	4	5	6	1
差值	1	1	1	1	1	1

注意到相同差值的位置可以通过旋转变成 $0$，所以 $k_{max}$ 就是最多的相同差值的数量，答案即为 $n-k_{max}$。

考虑如何构造目标环，首先设 $l_i, r_i$ 分别表示第 $i$ 个要求的相邻的点，钦定 $a_n=l_1, a_1=1$。接下来，每次判断第 $i$ 点的相邻两数是否在环中，若不在则加入进去，然后继续寻找新加入的这个点额相邻两数，知道环中的节点数为 $n$。

注意计算差值时，不能直接 $a_i-i$，需要加 $n$ 后 $\bmod{n}$。另外需要分别计算初始环顺时针和逆时针排列的方式。

Core Code

for (int i = 1; i <= n; i++) {
    if ((i != l[ l[i] ] && i != r[ l[i] ]) || (i != l[ r[i] ] && i != r[ r[i] ])) {
        cout << -1 << endl;
        return 0;
    }
}
a.push_back(0);
a.push_back(1);a.push_back(l[1]);
vis[1] = vis[l[1]] = 1;
int now = l[1];
while (a.size() != n + 1) {
    if (!vis[ l[now] ]) {
        a.push_back(l[now]);
        vis[l[now]] = 1;
        now = l[now];
    } else if (!vis[ r[now] ]) {
        a.push_back(r[now]);
        vis[r[now]] = 1;
        now = r[now];
    }
}
int maxn = 0;
for (int i = 1; i <= n; i++) {
    t[(a[i] + n - i) % n]++;
}
for (int i = 0; i < n; i++) {
    maxn = max(maxn, t[i]);
}
for (int i = 0; i <= n; i++) t[i] = 0;
for (int i = 1; i <= n; i++) {
    t[(a[i] + n - (n - i + 1)) % n]++;
}
for (int i = 0; i < n; i++) {
    maxn = max(maxn, t[i]);
}
cout << n - maxn << endl;

AT_joi2015ho_c JOI Park

Link

▶

题意

时值 $20\text{XX}$ 年，IOI 国为了给办奥赛做准备，将要修缮 IOI 国中的 JOI 公园。JOI 公园里有 $N$ 个广场，这些广场从 $1$ 到 $N$ 编号。有 $M$ 条道路连接各个广场，这些道路从 $1$ 到 $M$ 编号。第 $i(1 \leq i \leq M)$ 条道路是一条连接第 $A_i$ 和第 $B_i$ 个广场的双向边，长度为 $D_i$。任意两个广场间一定有道路（直接或间接）相连。

修缮计划如下：首先，选择一个自然数 $X$，将和第一个广场距离等于 $X$ 或在 $X$ 以下的所有广场（含第一个广场）相互之间连结一条地下通道。广场 $i$ 和广场 $j$ 的距离指，从广场 $i$ 到广场 $j$ 经过的道路长度总和的最小值。定义 $C$ 为一个与修筑地下通道花费有关的量（$C$ 是整数）。修筑所有地下通道的花费为 $C\times X$。

接下来，撤去已经通过地下通道连接的广场之间的道路。撤去道路的花费不计。

最后，将没有被撤去的道路进行修补，长为 $d$ 的道路修补的花费为 $d$。

修缮计划实施之前，JOI 公园没有地下通道。请求出 JOI 公园修缮花费总和的最小值。

需要注意的是删除的道路不只是 $1\to u$，还包含 $1\to u\to v(dis_u<dis_v)$。

tag: 最短路

Solution

首先注意到选择的 $X$ 一定是某一个点 $u$ 到 $1$ 节点的距离，所以先 Dijkstra 跑一遍预处理 $dis_u$，然后从小到大排序后枚举每个 $dis_u$ 来计算答案。比如样例中的遍历顺序为 $1, 3, 2, 4, 5$，可以发现，在枚举到靠后的节点时，它前面的所有点之间的路径都要被拆掉，这些点到当前节点的路径也要被拆掉（如果存在），所以当前拆掉的边可以由上一步拆掉的边转移而来，这也是从小到大的排序的意义。

一个例子，计算完 $2$ 后，$1\to 2$ 边会被删掉，按照上面的计算方法，下一步计算 $3$，此时应该拆掉 $1\to 3$ 和 $2\to 3$。

Core Code

#define int ll
int n, m, c;
struct node {
    int pos, dis;
    bool operator<(const node& x) const {
        return dis > x.dis;
    }
};
struct edge {
    int v, w;
};
vector<edge> e[N];
bitset<N> vis;
node dis[N];
int sum = 0ll;
void dij(int u) {
    for (int i = 1; i <= n; i++) {
        dis[i].dis = INF;
    }
    dis[1].dis = 0ll;
    priority_queue<node> q;
    q.push({1, 0});
    while (!q.empty()) {
        int u = q.top().pos;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1ll;
        for (auto x : e[u]) {
            int v = x.v, w = x.w;
            if (dis[v].dis > dis[u].dis + w) {
                dis[v].dis = dis[u].dis + w;
                if (!vis[v]) q.push({v, dis[v].dis});
            }
        }
    }
}
signed main() {
    n = read(); m = read(); c = read();
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read(), w = read();
        e[u].push_back({v, w});
        e[v].push_back({u, w});
        sum += w;
    }
    for (int i = 1; i <= n; i++) {
        dis[i].pos = i;
    }
    dij(1);
    sort(dis + 1, dis + n + 1);
    int minn = INF;
    int last = 0;
    vis.reset();
    for (int i = n; i >= 1; i--) {
        int ans = dis[i].dis * c;
        ans += sum;
        vis[dis[i].pos] = 1;
        for (auto x : e[dis[i].pos]) {
            int v = x.v, w = x.w;
            if (vis[v]) last += w;
        }
        minn = min(minn, ans - last);
    }
    cout << minn << endl;
    return 0;
}

AGC001C Shorten Diameter

给定一颗 $n$ 个节点的树，你需要删除一些叶子使得树的直径小于等于 $k$。求最少的删除的点的个数。

tag: 树的直径

Solution

将题目转化为寻找一个中心，使中心左右两边最多延伸 $\dfrac{k}{2}$ 个节点，记能延伸到的节点数为 $tot$。删除的点即为 $n-tot$。

如果 $k$ 是偶数，一定有一个中点，枚举中点即可。

如果 $k$ 是奇数，一定有相邻的两个中点，枚举即可。

Core Code

int tot;
void dfs(int u, int fa, int step) {
    tot++;
    if (step == 0) return;
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs(v, u, step - 1);
    }
}
int main() {
    int ans = INF;
    if (!(k & 1)) {
        for (int i = 1; i <= n; i++) {
            tot = 0;
            dfs(i, 0, k / 2);
            ans = min(ans, n - tot);
        }
    } else {
        for (int u = 1; u <= n; u++) {
            for (auto v : e[u]) {
                tot = 0;
                dfs(v, u, k / 2);
                dfs(u, v, k / 2);
                ans = min(ans, n - tot);
            }
        }
    }
}

P8677 [蓝桥杯 2018 国 A] 采油

Link

tag: 贪心

Solution

第一问显然最优情况下答案为边权和的两倍。

考虑第二问，对于一个点 $u$，至少需要耗费 $S_u$ 的人。

首先认为 $B_u\geq S_u$，因为即使 $B_u<S_u$，该节点也需要 $S_u$ 的人。

若只有一个节点，那么耗费的人显然为 $B_u$；

若有两个节点，不妨设为 $x$ 和 $y$，且 $B_x-S_x>B_y-S_y$，即 $x$ 剩下的人数比 $y$ 多，那么感性理解肯定要先走 $x$，才能充分发挥剩余的人。试图证一下，先 $x$ 后 $y$ 的总花费为 $\max\{B_x, B_x+B_y-(B_x-S_x)\}=\max\{B_x, B_y+S_x\}$，则先 $y$ 后 $x$ 的总花费为 $\max\{B_y, B_x+S_y\}$，将上面的式子移项可得 $B_y+S_x<B_x+S_y$，结论得证；

将结论推广到同一层上有 $k$ 个节点，可以通过两两依次缩点的形式转化为两个节点。

再考虑更一般的情况，在满足第一问的限制下，即按照最短路径，一定是先遍历完每个子树最短。所以搜到一个点时，先将这个点为根的所有子树缩点，按照剩余人数排序，递归继续缩点。

注意搜索时需要从 $B-S$ 最大的点开搜。

Core Code

struct node {
    int b, s;
    bool operator<(const node &x) const {
        return b - s > x.b - x.s;
    }
    node operator+(const node &x) const {
        node res;
        res.b = max(b, s + x.b), res.s = s + x.s;
        return res;
    }
}a[N];
node dfs(int u, int fa) {
    vector<node> p;
    p.push_back(a[u]);
    for (auto v : e[u]) {
        if (v == fa) continue;
        p.push_back(dfs(v, u));
    }
    node res;
    res.b = res.s = 0;
    sort(p.begin(), p.end());
    for (auto v : p) res = res + v;
    return res;
}
int main() {
    n = read();
    int sum = 0;
    int maxn = 0, maxpos = 1;
    for (int i = 1; i <= n; i++) {
        a[i].b = read();
    }
    for (int i = 1; i <= n; i++) {
        a[i].s = read();
        a[i].b = max(a[i].b, a[i].s);
        if (a[i].b - a[i].s > maxn) {
            maxn = a[i].b - a[i].s;
            maxpos = i;
        }
    }
    for (int i = 1; i < n; i++) {
        int v = read(), w = read();
        e[i + 1].push_back(v);
        e[v].push_back(i + 1);
        sum += w;
    }
    cout << sum * 2 << " " << dfs(maxpos, 0).b << '\n';
    return 0;
}

P2659 美丽的序列

Link

给定一个序列，找到一个区间使得区间最小值与区间长度的乘积最大，输出乘积。

tag: 单调栈

Solution

维护区间最小值，想到用单调栈。

单调递增栈，当遍历后面的元素时，如果此时元素比之前元素最小值小，那么之前元素的最小值地位从当前元素开始失效，也就可以得到之前元素所管辖的区间右端点。同理，也可以找到当前元素管辖区间的左端点，即为弹栈后的栈顶，也就是前面第一个大于当前元素的位置。

Core Code

for (int i = 1; i <= n; i++) {
    q[i].l = 1, q[i].r = n;
    while (!st.empty() && a[st.top()] > a[i]) {
        q[st.top()].r = i - 1;
        st.pop();
    }
    if (!st.empty()) q[i].l = st.top() + 1;
    st.push(i);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
    ans = max(ans, (q[i].r - q[i].l + 1) * a[i]);
}