BZOJ 2612 数学 构造 同余 最短路

Prob.

给一个集合 $ S, |S| < 5000, s_i < 10^9 $。
$ q < 5000 $ 组询问，问 $ x $ 是否可以表示为 $ \sum_i a_is_i, a_i \ge 0 $.

Sol.

可以视为今年 NOIp D1T1 的加强版了。

考虑模某一个数 $ a $，令 $ d_i $ 表示模 $ a $ 下余 $ i $ 能被表示的最小数。
显然有转移 $$ d_i + s_j \rightarrow d_{i+s_j~\text{mod}~a} $$。
直接计算是 $ O(n^2) $ 的。询问即等价于是否不小于对应余数的最小表示数。
但注意到封闭循环的性质，所以可以使用单源最短路来快速计算 $ d $。
使用 Dijkstra 可以做到 $ O(n \lg n) $，本题解决。
注意到令 $ a := \min S $ 可使常数最小。

BONUS

然而我没有用上述方法，我们考虑继续分析。
注意到每一个 $ d_i $ 均可表示成 $ i + k_ia $。
令$ a := \max S $，我们发现上述转移可以改写成 $$ k_i \rightarrow k_{i+s_j}, \text{if}~i+s_j<a \\\\ k_i + 1 \rightarrow k_{i+s_j-a}, \text{if}~i+s_j\ge a $$。
这是一个0/1最短路，bfs即可，复杂度$ O(n) $。

虽然理论上后者更优，但似乎在这道题前者跑得更快。

Code(1604 kb 1900 ms)

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 5e4 + 5, INF = 0x3f3f3f3f;
int k[maxn], a[maxn];
int Q[maxn], q[maxn];
int main()
{
    int n; read(n);
    int _max = 0;
    for(int i = 0; i < n; ++i) read(a[i]), _max = max(_max, a[i]);
    memset(k, INF, sizeof k); k[0] = 0;
    int h = 0, t = 0, H = 0, T = 0;
    q[t++] = 0;
    while(h != t)
    {
        Q[T++] = q[h++];
        int tH = H;
        while(H != T)
        {
            int u = Q[H++];
            for(int i = 0; i < n; ++i) if(u + a[i] < _max && k[u + a[i]] == INF)
                k[u + a[i]] = k[u], Q[T++] = u + a[i];
        }
        H = tH;
        while(H != T)
        {
            int u = Q[H++];
            for(int i = 0; i < n; ++i) if(u + a[i] >= _max && k[u + a[i] - _max] == INF)
                k[u + a[i] - _max] = k[u] + 1, q[t++] = u + a[i] - _max;
        }
    }
    int m; read(m);
    int b; while(m--) read(b), puts(b / _max < k[b % _max] ? "NIE" : "TAK");
    return 0;
}