UVA10036 Divisibility 题解

题目链接：UVA10036 Divisibility

题意：

考虑一个任意的整数序列。我们可以在序列中的整数之间放置+或-运算符，从而得到不同的算术表达式，其计算结果不同。例如，让我们考虑序列：$17,5,-21,15$。有八种可能的表达式：

$$\begin{aligned} & \texttt{17 + 5 + -21 + 15 = 16} \\ & \texttt{17 + 5 + -21 - 15 = -14} \\ & \texttt{17 + 5 - -21 + 15 = 58} \\ & \texttt{17 + 5 - -21 - 15 = 28} \\ & \texttt{17 - 5 + -21 + 15 = 6} \\ & \texttt{17 - 5 + -21 - 15 = -24} \\ & \texttt{17 - 5 - -21 + 15 = 48} \\ & \texttt{17 - 5 - -21 - 15 = 18} \end{aligned}$$

如果可以在序列中的整数之间放置 $\texttt{+}$ 或 $\texttt{-}$ 运算符，使得结果能被 $K$ 整除，则称该序列能被 $K$ 整除。在上述示例中，该序列能被 $7$ 整除（$\texttt{17 + 5 + -21 - 15 = -14}$），但不能被 $5$ 整除。 你需要编写一个程序来确定整数序列是否能被整除。

输入格式：

The first line of the input file contains a integer $M$ indicating the number of cases to be analyzed. Then $M$ couples of lines follow.

For each one of this couples, the first line of the input file contains two integers, $N$ and $K(1 \leq N \leq$ $10000,2 \leq K \leq 100$ ) separated by a space.

The second line contains a sequence of $N$ integers separated by spaces. Each integer is not greater than 10000 by it’s absolute value.

输出格式：

For each case in the input file, write to the output file the word ‘Divisible’ if given sequence of integers is divisible by $K$ or ‘Not divisible’ if it’s not.

经典题。设 $f_{i,j}$ 表示考虑前 $i$ 个数，是否存在至少一种组合使得最后的值 $!!\bmod K \equiv j$ 。

时间复杂度 $\mathcal{O}(\frac{nk}{\omega})$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e4 + 15))

bitset<115> f[N];
void solve()
{
    int n,k; cin >> n >> k;
    for(int i = 1; i <= n; i++) f[i] = 0;
    for(int i = 1, x; i <= n; i++)
    {
        cin >> x; x = (x % k + k) % k;
        if(i == 1) { f[1][x] = true; continue; }
        for(int j = 0; j < k; j++) if(f[i - 1][j]) {
            f[i][(j + x) % k] = f[i][(j - x + k) % k] = true;
        }
    }
    cout << (f[n][0] ? "Divisible" : "Not divisible") << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}