BZOJ 2118 墨墨的等式

2118: 墨墨的等式

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 2387 Solved: 936
[Submit][Status][Discuss]

Description

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

Input

输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。

Output

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

Sample Input

2 5 10
3 5

Sample Output

HINT

对于100%的数据，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。

Source

网上的题解看的人很晕，我开始完全没有往最短路上面去想，好吧根本就没有想233333

我们考虑一下这个答案肯定是符合前缀和的性质的，也就是说如果用sum[i]表示当B<=i时有多少个符合条件的解，那么定有sum[i]=sum[i-1]+t;

也就是说这道题我们求[L,R]，就可以可以转化为[1,R]的结果减去[1,L-1]的结果

首先对于任意一个ai，最后的结果都可以由k*ai+x来表示，如果没有ai的化，k就是0

x表示除了ai外剩下所有的a数组的总贡献对ai进行取模是多少也就是x=Σak*xk（k!=i）

因为对于任意一个都可以我们选取最小的那个来算，令minn=min(a[i]);也就是取所有a[i]的最小值（为什么选最小的最后我们分析复杂度的时候再讲）

首先我们肯定x是小于minn的我们既然选取了特定的ai也就是minn，那么x就是表示除了minn剩下的所有相加的和对minn取模的结果是多少

我们只要找出能满足x的最小花费是多少就可以了

建minn个点，dis[i]分别表示模minn意义下余i的能凑出的数最小为多少。对于每一个ai，从x向(x+ai)%minn连一条边权为ai的边。

求最短路，则最后求得dis[i]，计算一下就可以了。这个是建图代码

for(int i=0;i<a[1];i++){
for(int j=2;j<=n;j++){
insert(i,(i+a[j])%a[1],a[j]);
}
}

最后我门可以发现复杂度是minnlogminn，这就是我们为什么要选取最小的ai的原因

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    ll x=-0;int f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int MAXN=1e6+10;
struct node{
    int y,next,v;
}e[MAXN<<3];
ll linkk[MAXN],len=0,a[MAXN],dis[MAXN],vis[MAXN],n;
typedef pair <ll,ll> pii;
priority_queue < pii,vector<pii>,greater<pii> > q;
inline void insert(ll xx,ll yy,ll vv){
    e[++len].y=yy;e[len].next=linkk[xx];e[len].v=vv;linkk[xx]=len;
}
void dijsktra(){
    q.push(make_pair(0,0));
    dis[0]=0;
    while(!q.empty()){
        ll tn=q.top().second;q.pop();
        if(vis[tn]) continue;
        vis[tn]=1;
        for(int i=linkk[tn];i;i=e[i].next){
            if(dis[tn]+e[i].v<dis[e[i].y]){
                dis[e[i].y]=dis[tn]+e[i].v;
                q.push(make_pair(dis[e[i].y],e[i].y));
            }
        }
    }
}
inline bool mycmp(int x,int y){
    return x>y;
}
int main(){
    //freopen("All.in","r",stdin);
    //freopen("zh.out","w",stdout);
    n=read();ll L=read();ll R=read();
    memset(dis,127,sizeof(dis));
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    sort(a+1,a+n+1);
    for(int i=0;i<a[1];i++){
        for(int j=2;j<=n;j++){
            insert(i,(i+a[j])%a[1],a[j]);
        }
    }
    dijsktra();
    ll ans=0;
    for(int i=0;i<a[1];i++){
        if(R>=dis[i]) ans+=(R-dis[i])/a[1]+1;
        if(L-1>=dis[i]) ans-=(L-dis[i]-1)/a[1]+1;
    }
    cout<<ans<<endl;
    return 0;
}