Luogu | P2371 墨墨的等式 | 数论 / 图论 | 同余最短路

Description

墨墨突然对等式很感兴趣，他正在研究 $a_1x_1+a_2x_2+…+a_nx_n=B$ 存在非负整数解的条件，他要求你编写一个程序，给定 $N、{a_n}$、以及 $B$ 的取值范围，求出有多少 $B$ 可以使等式存在非负整数解。

Input Format

输入的第一行包含 $3$ 个正整数，分别表示 $N、B_{min}、B_{max}$ 分别表示数列的长度、$B$ 的下界、$B$ 的上界。

输入的第二行包含 $N$ 个整数，即数列 ${a_n}$ 的值。

Output Format

输出一个整数，表示有多少 $B$ 可以使等式存在非负整数解。

Input Sample

Sample 01

2 5 10
3 5

Output Sample

Sample 01

5

Data Range

$N \le 12$，$a_i \le 5 \times 10^5$，$1 \le B_{min} \le B_{max} \le 10^{12}$。

Solution

首先不难发现此题可以完全背包过部分数据。

将问题转化为求 $[0,B_{min}-1]$ 和 $[0,B_{max}]$ 两个区间的合法取值个数的差值。

设求 $[0,R]$ 中的合法取值。考虑将 $B$ 在同余类上分类讨论。设 $A$ 是 ${a_i}$ 中任意一个数，当原等式 $a_1x_1+a_2x_2+…+a_nx_n=B$ 成立时，设 $B \equiv x \mod A$，则原等式变为 $a_1x_1+a_2x_2+…+a_nx_n= kA + x$。在这里可以通过改变 $k$ 的值得到更多的取值。那么我们不妨找到一个最小的并且满足题目等式的 $kA + x$ 的值，之后在这个值的基础上变化 $k$ 即可。接下来放在同余类上讨论，若当前有某个值 $a_1x_1+a_2x_2+…+a_nx_n \mod A = y$，则考虑在此基础上加一个 $a_i$ 变为 $a_1x_1+a_2x_2+ … + a_i(x_i+1) + …+a_nx_n \equiv y+a_i \mod A$。转换为图论模型，即为从 $y$ 像 $y+a_i \mod A$ 连一条距离为 $a_i$ 的有向边。为 $\mod A$ 意义下的每个数都添加这些边，然后跑起点为 $0$ 的最短路，得到的 $dist_x$ 就是最小的并且满足题目等式的 $kA+x$。 这样，在 $\mod A = x$ 意义下能够变换的 $k$ 的数量即为 $\lfloor\frac{R-dist_x}{A}\rfloor + 1$ 个。枚举同余类 $x$ 统计答案即可。

实际操作时一般选最小的元素作为 $A$ 能使状态数最小，并且一定要忽略输入 $a_i$ 中的 0。

Code

#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::priority_queue;

typedef long long ll;

inline void Read(ll &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct pt{
    int id;
    int dist;
    friend bool operator < (pt a,pt b){
        return a.dist>b.dist;
    }
};

struct edge{
    int from;
    int to;
    int next;
    int w;
}e[6000005];

int N;
int minn;
int node;

ll L;
ll R;

int src[15];
int first[500005];
int last[500005];

ll dist[500005];

bool done[500005];

priority_queue<pt>pq;

void addedge(int u,int v,int w){
    e[++node]=(edge){u,v,0,w};
    if(first[u]==0) first[u]=node;
    else e[last[u]].next=node;
    last[u]=node; return;
}

void Dijkstra(){
    wipe(dist,0x3f);
    dist[0]=0;
    pq.push((pt){0,0});
    while(!pq.empty()){
        pt x=pq.top(); pq.pop();
        if(done[x.id])
            continue;
        done[x.id]=1;
        for(int p=first[x.id];p;p=e[p].next){
            int y=e[p].to;
            if(dist[y]>dist[x.id]+e[p].w){
                dist[y]=dist[x.id]+e[p].w;
                pq.push((pt){y,dist[y]});
            }
        }
    }
    return;
}

ll GetVal(ll x){
    ll ret=0;
    rep(i,0,minn-1)
        if(dist[i]<=x)
            ret+=(x-dist[i])/minn+1;
    return ret;
}

int main(){
    Read(N);
    Read(L);
    Read(R);
    rep(i,1,N)
        Read(src[i]);
    minn=500005;
    rep(i,1,N)
        if(src[i])
            minn=min(minn,src[i]);
    rep(i,0,minn-1)
        rep(j,1,N)
            if(src[j])
                addedge(i,(i+src[j])%minn,src[j]);
    Dijkstra();
    printf("%lld\n",GetVal(R)-GetVal(L-1));
    return 0;
}