公司建站模版,网站建设 北京,外包公司劳动合同,中国最新军事新闻 今天Description
众维拉先后在中土大陆上创造了精灵、人类以及矮人#xff0c;其中矮人是生性喜好常年居住在地下的洞穴的存在#xff0c;他们挖掘矿物甚至宝石#xff0c;甚至用他们的勤劳勇敢智慧在地底下创造出了辉煌宏大的宫殿#xff0c;错综复杂的迷宫——嗯#xff0c…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)必须有ux1,vy且从(x,y)到uv总共有b(v-y1)条通道直接连接。现在KPM无聊的想知道从入口出发到达第n行的第i个房间他总共有多少种走法由于他有数字恐惧症所以你只需要告诉他答案对19取模的结果即可。 Input
输入第一行包括三个整数nmk 输入第二行包括m个整数其中第i个整数为a(i) 输入第三行包括k个整数其中第i个整数为b(i)。 Output
输出包括一行该行包括m个整数其中第i个整数表示从入口到达(n,i)的方案数对19的取模注意只要经过的直接通路序列不同即算成不同方案。 Sample Input 3 2 2 3 4 1 2 Sample Output 3 16 Hint
样例解释
对于到达(n,1)经过的房间序列有一种S-(1,1)-(2,1)-(3,1)存在3113种通路情况
对于到达(n,2)经过的房间序列有三种分别为
S-(1,1)-(2,1)-(3,2),有3126种通路情况
S-(1,1)-(2,2)-(3,2),有3216种通路情况
S-(1,2)-(2,2)-(3,2),用4114中通路情况
因此到达(3,2)总有66416种通路情况。注S表示入口
数据范围与约定
对于10%的数据保证n,m1000,k10
对于另外20%的数据保证n10^18,m100
对于另外20%的数据保证n10^18,m400
对于剩下50%的数据保证n10^18,m10000
对于100%的数据保证a(i),b(i)5,km,min{n,m,k}0
solution
这种走迷宫的题求方案 已经是一种老套路了 一般都可以想象成矩阵×矩阵然后快速幂 设f[i][j]f[i][j]f[i][j]表示走到iii行jjj列的方案数 f[i][j]∑k0lim−1f[i−1][j−k]×b[k]f[i][j]\sum_{k0}^{lim-1}f[i-1][j-k]\times b[k]f[i][j]k0∑lim−1f[i−1][j−k]×b[k] FFTFFTFFT卷积转移n−1n-1n−1次用快速幂跑
code
#include cmath
#include cstdio
#include iostream
using namespace std;
#define mod 19
#define maxn 100005
struct complex {double x, i;complex(){}complex( double X, double I ) {x X, i I;}
}A[maxn], B[maxn];complex operator ( complex a, complex b ) {return complex( a.x b.x, a.i b.i );
}complex operator - ( complex a, complex b ) {return complex( a.x - b.x, a.i - b.i );
}complex operator * ( complex a, complex b ) {return complex( a.x * b.x - a.i * b.i, a.x * b.i a.i * b.x );
}double pi acos( -1.0 );int len 1;
int r[maxn];void FFT( complex *c, int f ) {for( int i 0;i len;i )if( i r[i] ) swap( c[i], c[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), f * sin( pi / i ) );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x c[j k], y w * c[j k i];c[j k] x y;c[j k i] x - y;}}}
}int m, k;
long long n;
int a[maxn], b[maxn];int main() {scanf( %lld %d %d, n, m, k );for( int i 1;i m;i )scanf( %d, a[i] );for( int i 0;i k;i ) //行已经差了1scanf( %d, b[i] );if( n 1 ) {for( int i 1;i m;i )printf( %d , a[i] );return 0;}int l 0;while( len ( m 1 ) ) {len 1;l ;}for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );for( int i 0;i m;i ) {A[i].x a[i];B[i].x b[i];}n --;while( n ) {if( n 1 ) {FFT( A, 1 );FFT( B, 1 );for( int i 0;i len;i ) A[i] A[i] * B[i];FFT( A, -1 );FFT( B, -1 );for( int i 0;i len;i ) {A[i] complex( ( ( int ) ( A[i].x / len 0.5 ) ) % mod, 0 );B[i] complex( ( ( int ) ( B[i].x / len 0.5 ) ) % mod, 0 );}}FFT( B, 1 );for( int i 0;i len;i ) B[i] B[i] * B[i];FFT( B, -1 );for( int i 0;i len;i )B[i] complex( ( ( int ) ( B[i].x / len 0.5 ) ) % mod, 0 );for( int i m 1;i len;i ) A[i].x B[i].x 0; //注意不要忘记清零n 1;}for( int i 1;i m;i ) printf( %d , ( ( int ) ( A[i].x 0.5 ) mod ) % mod );return 0;
}
