【UOJ267】【清华集训2016】魔法小程序（前缀和）-即速应用

【UOJ267】【清华集训2016】魔法小程序（前缀和）

浏览量：620 时间：2019-12-20 来源：Backseat-stargazer

传送门

可以显然 $c[i]$ 看出就是把 $a$ 作为该位进制时的数
满足每一位都不大于 $i$ 的 $j$ 的 $b[j]$ 的和

首先显然位数可以弄到 $O(log)$ ，把所有为1的 $a$ 跳过即可

然后~~乱减一下~~ 把其他所有多的 $b$ 减掉就可以把当前这一个求出来了

#includebits/stdc++.husing namespace std;#define cs const#define pb push_back#define pii pairint,int#define fi first#define se second#define ll long longcs int RLEN=120|1;inline char gc(){static char ibuf[RLEN],*ib,*ob;(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));return (ib==ob)?EOF:*ib++;}inline int read(){char ch=gc();int res=0;bool f=1;while(!isdigit(ch))f^=ch=='-',ch=gc();while(isdigit(ch))res=(res+(res2)1)+(ch^48),ch=gc();return f?res:-res;}inline ll readl(){char ch=gc();ll res=0;bool f=1;while(!isdigit(ch))f^=ch=='-',ch=gc();while(isdigit(ch))res=(res+(res2)1)+(ch^48),ch=gc();return f?res:-res;}cs int N=1000005,M=10005;int n,m,a[M],len;ll mt[M],c[N];int main(){#ifdef Stargazerfreopen("lx.cpp","r",stdin);#endifn=read(),generate(a+1,a+n+1,read);coutn'';for(int i=1;i=n;i++)couta[i]" ";puts("");m=read(),generate(c,c+m,readl);mt[0]=1;for(int i=1;i=n&&mt[len]=m;i++)if(a[i]!=1)mt[len+1]=mt[len]*a[i],len++;mt[len+1]=1e18,len++;for(int i=0;ilen;i++)for(int j=m-1;~j;j--)if(j%mt[i+1]/mt[i]0)c[j]-=c[j-mt[i]];coutm'';for(int i=0;im;i++)coutc[i]" ";}