[BZOJ 2118]墨墨的等式

danihao123 posted @ 2016年9月11日 15:16 in 题解 with tags SPFA 数论 数学 最短路 bzoj , 771 阅读
转载请注明出处:http://danihao123.is-programmer.com/

论如何把数论乱搞和图论乱搞出在一起……

这个题由于要求[tex]x\ge 0[/tex],所以不能gcd乱搞。我们可以先取[tex]\{a_n\}[/tex]的最小值[tex]p[/tex](忽略为0的情况,为啥取最小值待会再说),对方程两边模[tex]p[/tex]。然后对于任何能使某个同余方程成立的[tex]\{x_n\}[/tex],将其中所有[tex]x_i[/tex]同时加任意个[tex]p[/tex],同余方程都成立。

取模后,[tex]B\in Z_p[/tex],所以说只要对于[tex]Z_p[/tex]中的每个数找出最小的一组合法解即能推出其他解(所以说,剩余系越少效率越高,这也就要求取的[tex]a_i[/tex]要小)。不过这个最小的一组合法解怎么找?

我们先找出任意一个合法[tex]B[/tex](比如说0吧),然后尝试加上[tex]a_i[/tex],就可以推出其他[tex]B\in Z_p[/tex]的最小解。这个应用当然是需要最短路辣。

求出来的最短路,表示的是取最小解时的[tex]B[/tex]。这样的话就可以推出某个前缀区间中合法[tex]B[/tex]的个数(能加多少[tex]p[/tex],就有多少个,注意不要忽略加0个的情况),并且答案符合区间减法,最后做差分即可。

注意忽略[tex]a_i=0[/tex]的情况(相当于不存在)。

代码:

/**************************************************************
    Problem: 2118
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1952 ms
    Memory:5508 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
typedef long long ll;
const int maxn=15;
const ll INF=0x7f7f7f7f7f7f7f7f;
ll A[maxn];
bool inQueue[500005];
ll d[500005];
int n;
ll minv;
inline void SPFA(){
    register int i,u,to;
    queue<int> Q;
    memset(d,0x7f,sizeof(d));
    d[0]=0;
    Q.push(0);
    inQueue[0]=true;
    #ifdef DEBUG
    assert(d[1]==INF);
    #endif
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        inQueue[u]=false;
        for(i=1;i<=n;i++){
            to=(u+A[i])%minv;
            if(d[u]<INF && d[u]+A[i]<d[to]){
                d[to]=d[u]+A[i];
                if(!inQueue[to]){
                    Q.push(to);
                    inQueue[to]=true;
                }
            }
        }
    }
}
 
inline ll Calc(ll x){
    register ll ans=0;
    register int i=0;
    for(i=0;i<minv;i++)
        if(d[i]<=x)
            ans+=(x-d[i])/minv+1;
    return ans;
}
 
int main(){
    ll l,r;
    register int i;
    scanf("%d%lld%lld",&n,&l,&r);
    minv=0x7fffffff;
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        if(!A[i]){
            i--;
            n--;
            continue;
        }
        minv=min(minv,A[i]);
    }
    SPFA();
    printf("%lld\n",Calc(r)-Calc(l-1));
    return 0;
}

AP 1st Inter Botany 说:
Sep 08, 2022 07:31:42 PM

In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 1st Inter Botany Model Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter