uoj#267. 【清华集训2016】魔法小程序（乱搞）
感觉很像FFT的过程的说……
先来考虑(b)如何转化成(c)，那么只要通过它的逆过程就可以了
首先，我们称“魔法”为比较两个数的字典序，记(x=a_0)，那么把(b)数组每(x)个分为一组，在每组里面，(b_i\%x)的值都是递增的，也就是说对于同一组里面的每一对(i<j)，(i)的字典序都小于(j)的字典序。根据代码，(c[j])最终的值是所有(ileq j)且(i)的字典序小于等于(j)的所有(b[i])之和。排除掉(j)自己，就是所有比它小且字典序比它小的(b[i])之和
如果(i)的字典序小于(j)的字典序，那么就要(c[j]+=b[i])，那么设其中一组为([l,r])，我们从左到右枚举(iin[l,r-1])，并令(b[i+1]+=b[i])，因为这相当于是一个前缀和的过程，所以对于每一个(b[i])，它都加上了所有(b[j](j<i))
字典序第一维不同的情况考虑完了，那么考虑第一维相同而第二维不同，令(y=a_0 imes a_1)，然后每(y)个分为一组，那么对于同一组里(i)和(i-x)是第一维相同而第二维不同的，所以(b[i])要加上(b[i-x])。
那么只考虑第二维会不会漏掉第一维的情况？比方说在第一次分组时，(j)位于第(2)组，(i)为与第(1)组，且(i)的字典序比(j)小，(i)就没有加上去。实际上不会有这样的情况，因为我们第一次分组时已经前缀和过了，所以此时(b[i])的值肯定已经加到(b[j-x])中了，所以不会出现漏减的情况
综上，要令(b)变为(c)，记(sum_i)为(a_i)的前缀积，我们要依次枚举(sum_i)，分组后在内部从左到右枚举，令每个(b[j])加上(b[j-sum_{i-1}])
于是要令(c)变为(b)，只要将这个过程反过来就可以了，只要倒着枚举前缀积，从右往左枚举(j)，令每个(c[j])减去(c[j-sum_{i-1}])即可
//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
ll read(){
R ll res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]=' ';
}
const int N=1e6+5,M=1e4+5;
int a[M],b[N],las[N],tmp[N],st[N];ll c[N];
int n,m,top,tt;
void out(){
print(n),sr[C]='
';
fp(i,0,n-1)print(a[i]);sr[C]='
';
print(m),sr[C]='
';
fp(i,0,m-1)print(c[i]);sr[C]='
';
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();
fp(i,0,n-1)a[i]=read();
m=read();
fp(i,0,m-1)c[i]=read();
st[++top]=1;
for(R int i=0;i<n&&1ll*st[top]*a[i]<=m;++i)
if(a[i]!=1)++top,st[top]=st[top-1]*a[i];
st[++top]=m+1;
for(R int mid=st[top];top>1;mid=st[--top]){
for(R int i=0;i<m;i+=mid){
int j=min(i+st[top]-1,m-1);
while(j>=i+st[top-1])c[j]-=c[j-st[top-1]],--j;
}
}
out();
return Ot(),0;
}