Storage Problems ( 2020-2021 ICPC Central Europe Regional Contest (CERC 20) )

The gangsters did a very successful robbery of the city’s most famous auction house. Now they are safely at their hideout, where they store the stolen items. Luckily, you managed to place a listening device into their hideout. You also have a personal file on each ganger, which contains a recording of their voice. You will listen carefully to what happens next with hope it will help you with the investigation of the robbery.

Each gangster stole exactly one item, the $i$-th gangster stole the $i$-th item. Now each gangster is trying to put his item into the common storage, which can hold a total weight of $K$. The storage is a small room and the gangsters store their items one by one.

When a gangster tries to put an item into the storage but it does not fit, that is the total weight of the items in the storage would exceed $K$, he gets angry and throws all the items in the storage out. While doing this, he tells the others that “$j$ items are going to trash!”, where $j$ is the number of items in the storage at the point he tried to store his item. At this point a fight ensues and no more storing will happen.

As you have a listening device in the gangsters’ storage, you will hear how much items the gangster throws out. Also, using your personal files, you can tell apart each of the gangster’s voices.

Therefore, it would help your investigation greatly if you could know in advance, for all possible values of $j$ and $i$, how many different subsets of items could be in the storage at the moment when the $i$-th gangster throws all the $j$ items out. As the number of subsets can be large, output it modulo $167772161$.

Input

The input consists of two lines. The first line contains two integers $N$ and $K$ ($2\le N\le 400$, $1\le K\le 400$), the number of gangsters and the maximum weight that the storage can hold. The second line contains $N$ integers $w_1,w_2,\cdots ,w_N$, such that ($1\le w_i\le K$) for each $1\le i\le N$. Here wi is the weight of item that the $i$-th gangster stole.

Output

The output consists of $N$ lines, each line containing exactly $N-1$ integers. The $j$-th value on the $i$-th line contains the number of subsets of items containing exactly $j$ items, such that they fit into the storage but the $i$-th gangter’s item can not be added. Each number is modulo $167772161$.

Examples

Input

3 3
2 2 1

Output

1 1
1 1
0 0

Input

5 5
1 2 3 4 5

Output

1 1 0 0
2 2 0 0
2 2 0 0
3 3 0 0
4 4 0 0

题面描述

题目描述了一群劫匪成功抢劫了城市中最著名的拍卖行，并将赃物藏匿在他们的藏身处。每个劫匪都偷了一件物品，第 (i) 个劫匪偷了第 (i) 件物品。现在，每个劫匪都试图将自己的物品放入一个总承重为 (K) 的公共储物室中。储物室是一个小房间，劫匪们依次将物品放入其中。

当一个劫匪试图将物品放入储物室时，如果物品的总重量超过了 (K)，他会生气并将储物室中的所有物品都扔出去。同时，他会告诉其他人：“(j) 件物品要被扔掉了！”，其中 (j) 是储物室中当前物品的数量。此时，劫匪们会开始打架，之后不会再进行任何存储操作。

你有一个监听设备，可以听到劫匪们扔出物品的数量。同时，你还可以通过劫匪的声音分辨出每个劫匪的身份。因此，你需要提前计算出对于所有可能的 (j) 和 (i)，当第 (i) 个劫匪扔掉 (j) 件物品时，储物室中可能存在的不同物品子集的数量。由于子集数量可能很大，输出结果需要对 (167772161) 取模。

输入

输入包含两行。第一行包含两个整数 (N) 和 (K)（(2 \leq N \leq 400)，(1 \leq K \leq 400)），分别表示劫匪的数量和储物室的最大承重。第二行包含 (N) 个整数 (w_1, w_2, \cdots , w_N)，其中 (1 \leq w_i \leq K)，表示第 (i) 个劫匪偷的物品的重量。

输出

输出包含 (N) 行，每行包含 (N - 1) 个整数。第 (i) 行的第 (j) 个值表示当第 (i) 个劫匪扔掉 (j) 件物品时，储物室中可能存在的不同物品子集的数量。每个数字需要对 (167772161) 取模。

题解

这道题目可以通过动态规划来解决。我们需要计算在每一步操作中，储物室中可能存在的物品子集的数量。具体来说，我们需要考虑每个劫匪在尝试放入物品时，储物室中已有的物品子集是否会导致总重量超过 (K)。

1. 初始化：我们使用一个二维数组 dp[j][k] 来表示在前 (i) 个物品中，选择 (j) 个物品且总重量为 (k) 的子集数量。初始时，dp[0][0] = 1，表示不选择任何物品时，总重量为 0 的子集数量为 1。

2. 动态规划：对于每个物品 (i)，我们更新 dp 数组。具体来说，对于每个可能的物品数量 (j) 和总重量 (k)，如果前 (i-1) 个物品中存在 (j-1) 个物品且总重量为 (k - w_i) 的子集，那么我们可以将第 (i) 个物品加入这些子集中，从而得到 (j) 个物品且总重量为 (k) 的子集。

3. 计算每个劫匪的结果：对于每个劫匪 (i)，我们需要计算当他尝试放入物品时，储物室中已有的物品子集是否会导致总重量超过 (K)。我们可以通过遍历所有可能的物品数量 (j) 和总重量 (k)，并检查 (k + w_i > K) 的情况来得到结果。

4. 输出结果：对于每个劫匪 (i)，输出所有可能的 (j) 值对应的子集数量。

代码分析

#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int inf = 1e9 + 7;
const int N = 400 + 10;
const int mod = 167772161;

int n, K;
int w[N];
vector<vector<int>> dp(N, vector<int>(1000));
vector<vector<int>> dp1(N, vector<int>(1000));
int vis[N][3 * N];

void solved()
{
    cin >> n >> K;
    for (int i = 1; i <= n; ++i)
    {
        cin >> w[i];
    }

    dp[0][0] = 1;
    vis[0][0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i; j >= 1; --j)
        {
            for (int k = 800; k >= w[i]; --k)
            {
                if (vis[j - 1][k - w[i]])
                {
                    dp[j][k] = (dp[j][k] + dp[j - 1][k - w[i]] + mod) % mod;
                    vis[j][k] = 1;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        dp1 = dp;
        for (int j = 0; j <= n; j++)
        {
            for (int k = 0; k <= K; k++)
            {
                if (vis[j][k] and vis[j + 1][k + w[i]])
                {
                    dp1[j + 1][k + w[i]] = (dp1[j + 1][k + w[i]] - dp1[j][k] + mod) % mod;
                }
            }
        }
        for (int j = 1; j <= n - 1; j++)
        {
            int ans = 0;
            for (int k = 0; k <= K; k++)
            {
                if (k + w[i] > K)
                {
                    ans = ans + dp1[j][k] % mod;
                    ans %= mod;
                }
            }
            cout << ans << " ";
        }
        cout << endl;
    }
}

signed main()
{
    BoBoowen;

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solved();
    }
}

代码分析

1. 初始化：dp[0][0] = 1 表示不选择任何物品时，总重量为 0 的子集数量为 1。vis 数组用于记录哪些状态是可达的。

2. 动态规划：对于每个物品 (i)，从后向前更新 dp 数组。如果前 (i-1) 个物品中存在 (j-1) 个物品且总重量为 (k - w_i) 的子集，那么我们可以将第 (i) 个物品加入这些子集中，从而得到 (j) 个物品且总重量为 (k) 的子集。

3. 计算每个劫匪的结果：对于每个劫匪 (i)，我们复制 dp 数组到 dp1，然后遍历所有可能的物品数量 (j) 和总重量 (k)，并检查 (k + w_i > K) 的情况。如果满足条件，则将 dp1[j][k] 加入结果中。

4. 输出结果：对于每个劫匪 (i)，输出所有可能的 (j) 值对应的子集数量。

总结

这道题目通过动态规划的方法，计算了在每个劫匪尝试放入物品时，储物室中可能存在的不同物品子集的数量。代码通过维护一个二维数组 dp 来记录不同物品数量和总重量下的子集数量，并通过遍历和更新来得到最终的结果。