【My Problem】对联

Author Avatar
洛水·锦依卫 1月 26, 2019

题面

Notice:本题数据较大,建议使用较快的读入方式

Background

新春写对联一直是传统的习俗啊!天依阿绫铺开纸张,在长长的案桌上研墨,准备开始写对联啦,而其余人正在旁边眼巴巴地看着。

龙牙:我要一个帅气奢华的对联!最好要有 $123,345,567$ 个字!

摩柯:我要一个关于对高个子的控诉的对联!最好有 $e^{\omega^{\alpha^{2000}}}$ 个字!

大家的要求太多啦!总共就那么多可以使用的词汇,大家要求的对联长度还真不一定能组合出来,于是天依想请你帮帮忙,告诉她使用已有的词汇能够写出大家的长度要求下多少种长度的对联。

Description

天依总共会 $n​$ 种词汇,第 $i​$ 种词汇长度为 $a_i​$ ,确保每个词汇长度不同。总共有 $m​$ 个人找天依写对联,已知第 $i​$ 个人要求对联长度不超过 $p_i​$,天依希望能知道对于第 $i​$ 个人,她用这 $n​$ 种词汇能写出多少种不大于 $p_i​$ 的对联长度。(每个词汇可以反复使用)

输入格式

一行两个整数 $n$ 和 $m​$ 。

接下来一行 $n$ 个数,表示各个词汇的长度。

接下来一行 $m$ 个数,表示各个人的对联要求长度。

输出格式

$m$ 行,每行一个整数表示每个询问的答案。

输入输出样例

输入样例1

2 3
5 3
3 16 8

输出样例1

1
12
4

样例解释:对于长度为 $3,5,6,8,9,10,11,12,13,14,15,16$ 的对联我们都可以写出,分别对应每个上限即可。

输入样例2

4 2
38642 20254 43579 43773 
31565 59294

输出样例2

1
6

数据范围

对于 $10\%$ 的数据,$n<=4,m<=2,\forall p_i<=10^5$

对于 $50\%$ 的数据,$m<=100$

对于 $100\%$ 的数据,$n<=13,m<=10^6,\forall p_i<=10^{18},\forall a_i<=5*10^5$ 。

题解

考点

最短路,建图,动态维护区间和的数据结构(树状数组或线段树),排序算吗

10pts

非常裸,一遍完全背包,拿数组记前缀和,每次询问对应下标输出。

50pts

我们首先考虑这样一个问题:如果 $m=1$ ,我们该如何统计呢?

首先我们选出任意一个 $a_x$ 。(真的是任意,不过建议选最小的那个数),把统计答案先放放哈 = = 。

首先假设我们当前能组合一个长度 $j$ 的对联,我们就一定能组合出长度为 $j+1*a_x,j+2*a_x,j+3*a_x$…… 的对联,这是显然的。那么,如果组合出 $j$ 长度的过程中使用了长度为 $a_x$ 的对联,我们也必能反推出 $j-a_x$ 是能够表示的。

当我们不断地减去 $a_x$ ,直到 $j-k*a_x$ 是无法使用任何一次 $a_x$ 组合得到,这时我们便发现 :

$j-k*a_x+1*a_x,j-k*a_x+2*a_x$…… 这样的长度是必定可以得到。

这种时候我们思考一个事实:不难发现,当我们得到这样一个 $j-k*a_x$ 之后,对于任何一个长度为 $i$ 的对联,如果 $i\ mod\ a_x=j\ mod\ a_x$ ,并且 $i>=j-k*a_x$ 的话,$i$ 长度必定可以由 $j-k*a_x$ 与若干个 $a_x$ 组合出来。同时由此可以证明对于不同的 $j\ mod\ a_x$ ,它们具有 $j-k*a_x$ 上的唯一性,因为对于任意一个 $i\ mod\ a_x=j\ mod\ a_x$,它同样可以表示成 $i-k_2\ a_x=j-k\ a_x$ 。

所以我们只需要求出对于每个 $q<x$ 的情况下,$i\ mod\ a_x=q$ 的 $i-k_2*a_x$。由于唯一性,我们只需要求出 $i\ mod\ a_x=0~x-1$ 的这 $x$ 个值即可。由于每个 $i-k_2*a_x$ 都无法再分解出 $a_x$ 来,问题就转化了:

(最重点)我们需要求出对于任意一个 $q<a_x$,不使用 $a_x$ 这个词语,能够组成的,最短的的,对 $a_x$ 取模结果为 $p$ 的对联长度(这里可能要多想一会儿)

对于这个,我们可以建图来跑最短路:对于任意一个 $p<a_x$ 向 $(p+a_i)\%a_x~~(1<=i<=n\&\&i!=x)$ 连一条长度为$a_i$ 的边,$dis[0]=0$ (因为写一个 $mod~a_x=0$ 的对联最短的情况就是不用任何一个单词) ,并以 $0$ 为起点,最后得到的 $dis[0~a_x-1]$ 即为每个 $p<a_x$ 下最短的,对 $a_x$ 取模等于 $p$ 的对联长度。

那么对答案的统计就很简单了吧:对于任意一个 $dis[p]$ 而言,$dis[p]+a_x,dis[p]+2*a_x……$ 都是可以组合出来的,那么对于单个的要求,设最长长度为 $len$ ,答案即为:

为什么要 $+1$ 呢?因为 $dis[p]$ 这个长度本身就是可以组合出来的呀 $QwQ$

求出最短路后,对于每个答案做一遍求和就能有 $50$ 分啦!

100pts

好滴,我们来考虑统计 $m​$ 个 $\sum​$ 的答案吧!

首先我们就能发现,$dis$ 数组的下标现在已经是毫无意义的了,排序!

然后发现询问非在线,再排序!

那么我们发现对于当前询问,必定有一个 $i$ 使得 $dis[0]~dis[i]$ 小于等于询问值,而 $dis[i+1]~dis[a_x-1]$ 则大于询问值,而因为询问已经离线,那么 $i$ 必定是从左向右不断移动的。那么不难想到,对于移动过程中新增的可以计算对询问贡献的 $dis$ 值,答案中直接加入 $(询问值-dis)/a_x+1$ 即可,那么对于已经计算过的之前的 $dis$ 的贡献怎么算呢?

首先设此次询问之前有 $i​$ 个 $dis​$ 值已计算,那么首先我们必定有 $((当前询问-上一次询问)/a_x)*i​$ 这一部分的贡献。

然后呢?我们对每个 $dis​$ 分开考虑,对于每个 $dis​$ 而言,询问值每比它高上 $a_x​$ 它的贡献都会加一。由于每个 $dis​$ 排序之前下标模 $a_x​$ 的唯一性,不难发现,我们只需要维护这样一个序列 $p​$(这里好好想一想):

对于已经计算过的 $dis[i]$ 我们在序列中的 $id[i]$ (也即原下标) 的位置加一($p[id[i]]++$),我们假设有一个指针 $top$ ,那么对于当前询问,$top=询问值\%a_x$ ,然后到下一个询问时,$top$ 向右跳 下一个询问-当前询问 步,每当到达 $a_x-1$ 之后,下一步回到 $0$ ,在这个过程中 $ans+=p[top]$ ,即一旦经过有值的位置,对答案贡献 $+1$ 。而之前的那部分贡献则是优化这个跳的过程,另这一过程最多跳 $a_x$ 步。当然这样显然还是莫得意义的。那么对于这个跳的步骤,用能维护区间和的数据结构维护跳出去的这一段中的 $1$ 的数量即可。

$100$ 分就是这样了。

个人认为能想到 $50$ 分那么 $100$ 分就没什么问题了。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,a[14],cnt,head[500001],nx[6000001],to[6000001],w[6000001],m,top,now;
bool u[500001];
long long dis[500001],c[500001],limit,ans,Ans[1000001];
struct node
{
    long long H;
    int d;
}k[1000001];
struct num
{
    long long dis;
    int d;
}p[500001];
bool cmp(node a,node b)
{
    return a.H<b.H;
}
bool cmp2(num a,num b)
{
    return a.dis<b.dis;
}
void add(int u,int v,int W,int d)
{
    to[d]=v,w[d]=W,nx[d]=head[u];
    head[u]=d;
}
queue <int> q;
void SPFA()
{
    q.push(0);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        u[x]=0;
        for(int i=head[x];i;i=nx[i])
            if(dis[to[i]]>dis[x]+w[i])
            {
                dis[to[i]]=dis[x]+w[i];
                if(!u[to[i]])
                {
                    u[to[i]]=1;
                    q.push(to[i]);
                }
            }
    }
}
void add(int k)
{
    for(int i=k;i<=limit;i+=i&-i)
        c[i]++;
}
long long query(int k)
{
    long long ans=0;
    for(int i=k;i>0;i-=i&-i)
        ans+=c[i];
    return ans;
}
int main()
{
    freopen("couplet.in","r",stdin);
    freopen("couplet.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&k[i].H);
        k[i].d=i;
    }
    sort(a+1,a+n+1);
    limit=(long long)a[1];
    for(int i=0;i<a[1];i++)
    {
        dis[i]=2e18;
        for(int j=2;j<=n;j++)
            add(i,(i+a[j])%a[1],a[j],++cnt);
    }
    dis[0]=0;
    SPFA();
    for(int i=0;i<a[1];i++)
    {
        p[i].d=i;
        p[i].dis=dis[i];
    }
    sort(p+0,p+a[1],cmp2);
    sort(k+1,k+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        long long chan=k[i].H-k[i-1].H;
        ans+=(chan/limit)*query((int)limit);
        chan%=limit;
        if(chan+now>limit-1)
        {
            ans+=query(limit)-query(now+1);
            now=k[i].H%limit;
            ans+=query(now+1);
        }
        else
        {
            ans+=query(now+chan+1)-query(now+1);
            now+=chan;
        }
        while(p[top].dis<=k[i].H&&top<a[1])
        {
            ans+=(k[i].H-p[top].dis)/limit+1;
            add(p[top].d+1);
            top++;
        }
        Ans[k[i].d]=ans;
    }
    for(int i=1;i<=m;i++)
        printf("%lld\n",Ans[i]-1);
}