Description
众维拉先后在中土大陆上创造了精灵、人类以及矮人，其中矮人是生性喜好常年居住在地下的洞穴的存在，他们挖掘矿物甚至宝石，甚至用他们的勤劳勇敢智慧在地底下创造出了辉煌宏大的宫殿，错综复杂的迷宫——嗯，没错，现在KPM这个毛小孩要扯上关系的就是迷宫啦~
描述
KPM在矮人的王国发现了一个迷宫，现在这个迷宫是这样的：迷宫的主体由排列成一个整齐的n行m列的矩阵的房间组成，同一行或者是同一列之中相邻的房间的距离为1，我们用（x,y）来表示第x行的第y列的房间，然后KPM惊奇的发现，迷宫的入口（不包含在矩阵状的房间中）与第一行的所有房间之间都有通道连接，其中与第i个房间连接的通道数目为a(i)，然后对于任意两个房间(x,y),(u,v)，当且仅当两个房间之间的曼哈顿距离不大于k且处于相邻的两行，即|x-u|+|y-v|<=k,且|x-u|=1,房间直接存在通道连接,然后根据KPM第XX定律，KPM发现对于入口到第一行房间的所有通道，KPM只能通过其从入口走向房间，却没办法反过来走，对于两个房间(x,y),(u,v)，假如两个房间之间存在连边，KPM只能从行数小的那行走到行数大的那行，而且还要保证他走过的房间的列数是单调不递减的，而且，这如果这两个房间之间的曼哈顿距离为d，这两个房间的直接相连通道数目为b(d),也就是说，假如KPM可以从(x,y)走到(u,v)，必须有u=x+1,v>=y，且从(x,y)到（u，v）总共有b(v-y+1)条通道直接连接。现在，KPM无聊的想知道，从入口出发，到达第n行的第i个房间，他总共有多少种走法，由于他有数字恐惧症，所以你只需要告诉他答案对19取模的结果即可。
Input
输入第一行包括三个整数n，m，k；
输入第二行包括m个整数，其中第i个整数为a(i)；
输入第三行包括k个整数，其中第i个整数为b(i)。
Output
输出包括一行，该行包括m个整数，其中第i个整数表示从入口到达(n,i)的方案数对19的取模（注意：只要经过的直接通路序列不同即算成不同方案）。
Sample Input
3 4
1 2
Sample Output
解题思路：
考虑只能往下走，和往右下走，每一行的每一处的转移方案都可以认为是上一行的某处方案×$b_{曼哈顿距离}$
所以可以认为是a数组上乘了n-1个b数组，n太大多项式快速幂解决就好了。
PS：以前没做过这类题目FFT中m项以后的数都是要删除的否则会一下答案。
代码：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long lnt;
const int N=;
const double PI=acos(-1.0);
struct cp{
double x,y;cp(){};cp(double a,double b){x=a;y=b;}
cp friend operator + (cp a,cp b){return cp(a.x+b.x,a.y+b.y);}
cp friend operator - (cp a,cp b){return cp(a.x-b.x,a.y-b.y);}
cp friend operator * (cp a,cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
}B[N],C[N];
lnt n;
int m,k;
int lim,len;
int pos[N];
int Aa[N],Bb[N];
void FFT(cp *a,double flag)
{
for(int i=;i<len;i++)
if(i<pos[i])
std::swap(a[i],a[pos[i]]);
for(int i=;i<=len;i<<=)
{
cp wn(cos(2.00*PI*flag/(double)(i)),sin(2.00*PI*flag/(double)(i)));
for(int j=;j<len;j+=i)
{
cp w(1.00,0.00),t;
for(int k=;k<(i>>);k++,w=w*wn)
{
t=a[j+k+(i>>)]*w;
a[j+k+(i>>)]=a[j+k]-t;
a[j+k]=a[j+k]+t;
}
}
}
return ;
}
int main()
{
scanf("%lld%d%d",&n,&m,&k);
memset(Bb,,sizeof(Bb));
for(int i=;i<=m;i++)scanf("%d",&Aa[i]);
for(int i=;i<k;i++)scanf("%d",&Bb[i]);
if(n==)
{
for(int i=;i<=m;i++)printf("%d ",Aa[i]);
return ;
}
while((<<lim)<=*m)lim++;
len=<<lim;
for(int i=;i<len;i++)pos[i]=(pos[i>>]>>)|((i&)<<(lim-));
for(int i=;i<=m;i++)
{
C[i].x=Aa[i];
B[i].x=Bb[i];
}
n--;
while(n)
{
if(n&)
{
FFT(C,1.0);
FFT(B,1.0);
for(int i=;i<len;i++)C[i]=C[i]*B[i];
FFT(C,-1.0);
FFT(B,-1.0);
for(int i=;i<len;i++)
C[i]=cp(((int)(C[i].x/len+0.1))%,0.00),
B[i]=cp(((int)(B[i].x/len+0.1))%,0.00);
}
FFT(B,1.0);
for(int i=;i<len;i++)B[i]=B[i]*B[i];
FFT(B,-1.0);
for(int i=;i<len;i++)B[i]=cp(((int)(B[i].x/len+0.1))%,0.00);
for(int i=m+;i<len;i++)C[i].x=B[i].x=0.00;
n=n/;
}
for(int i=;i<=m;i++)
printf("%d ",((int(C[i].x+0.1))+)%);
puts("");
return ;
}