网站后台加什么后缀,网站开发属于什么职位类别,wordpress社交系统,joomla 2.5:你的网站建设_使用与管理Description
小C有一个集合S#xff0c;里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器#xff0c;可以生成一个长度为N的数列#xff0c;数列中的每个数都属于集合S。小C用这个生成器生成了许多这样的数列。 但是小C有一个问题需要你的帮助#xff1a;给定…Description
小C有一个集合S里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器可以生成一个长度为N的数列数列中的每个数都属于集合S。小C用这个生成器生成了许多这样的数列。 但是小C有一个问题需要你的帮助给定整数x求所有可以生成出的且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。 小C认为两个数列{Ai}和{Bi}不同当且仅当至少存在一个整数i满足Ai≠Bi。另外小C认为这个问题的答案可能很大因此他只需要你帮助他求出答案mod 1004535809的值就可以了。
Input 一行四个整数N、M、x、|S|其中|S|为集合S中元素个数。 第二行|S|个整数表示集合S中的所有元素。 1N10^93M8000M为质数 0xM-1输入数据保证集合S中元素不重复x∈[1,m-1] 集合中的数∈[0,m-1]
Output 一行一个整数表示你求出的种类数mod 1004535809的值。
Sample Input 4 3 1 2 1 2 Sample Output 8
【样例说明】 可以生成的满足要求的不同的数列有(1,1,1,1)、(1,1,2,2)、(1,2,1,2)、(1,2,2,1)、 (2,1,1,2)、(2,1,2,1)、(2,2,1,1)、(2,2,2,2)
solution
设f[i][j]f[i][j]f[i][j]表示选了iii个数的乘积%mj\%mj%mj的方案数 f[i1][j]∑(j1×j2)%mjf[i][j1]×f[i][j2]f[i1][j]\sum_{(j_1\times j_2)\%mj}f[i][j_1]\times f[i][j_2]f[i1][j](j1×j2)%mj∑f[i][j1]×f[i][j2] 乘法目前来说是超越知识 那么将相乘转化为指数上的相加暴艹出mmm的原根 题目保证了mmm是质数一定会有原根 f[i1][j]∑(j1j2)%mjf[i][j1]×f[i][j2]f[i1][j]\sum_{(j_1j_2)\%mj}f[i][j_1]\times f[i][j_2]f[i1][j](j1j2)%mj∑f[i][j1]×f[i][j2] 这就长得很像可以卷积的玩意儿 涉及取模那就用NTTNTTNTT 但是这个跟普通的式子下面的条件略有不同j1j2jj_1j_2jj1j2j [m−1,2m−2][m-1,2m-2][m−1,2m−2]这里面也会对答案有贡献被m−1m-1m−1取模
code
#include cmath
#include cstdio
#include iostream
using namespace std;
#define int long long
#define mod 1004535809
#define maxn 20000
int g, len 1, inv;
int r[maxn], ans[maxn], f[maxn], fi[maxn];int qkpow( int x, int y, int MOD ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % MOD;x x * x % MOD;y 1;}return ans;
}void NTT( int *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 ) {int omega qkpow( ( f 1 ) ? 3 : mod / 3 1, ( mod - 1 ) / ( i 1 ), mod );for( int j 0;j len;j ( i 1 ) ) {int w 1;for( int k 0;k i;k , w w * omega % mod ) {int x c[j k], y w * c[j k i] % mod;c[j k] ( x y ) % mod;c[j k i] ( x - y mod ) % mod;}}}if( f -1 ) {for( int i 0;i len;i )c[i] c[i] * inv % mod;}
}void root( int m ) {int phi m - 1;for( int i 2;i m;i ) {bool flag 1;int x phi;for( int j 2;j * j x;j ) {if( phi % j ) continue;while( x % j 0 ) x / j;if( qkpow( i, phi / j, m ) 1 ) {flag 0;break;}}if( x 1 qkpow( i, phi / x, m ) 1 ) continue;if( flag ) {g i;return;} }
}signed main() {int n, m, x, s;scanf( %lld %lld %lld %lld, n, m, x, s );root( m );for( int i 0;i m - 1;i ) fi[qkpow( g, i, m )] i;
//g^i_(mod m) 相乘转化为指数相加 指数相加就可以用NTT暴艹卷积 for( int i 1, a;i s;i ) {scanf( %lld, a );if( ! a ) continue;else f[fi[a]] ;}int l 0;while( len ( ( m - 1 ) 1 ) ) {len 1;l ;}inv qkpow( len, mod - 2, mod );for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );ans[0] 1;while( n ) {if( n 1 ) {NTT( f, 1 );NTT( ans, 1 );for( int i 0;i len;i ) ans[i] ans[i] * f[i] % mod;NTT( f, -1 );NTT( ans, -1 );for( int i m - 1;i len;i )
//a^b_(%p)a^[b%phi(p)]_(%p) 指数以m-1为一个循环节 在%m后应该都是一样的 对最后%mx的答案可能会有贡献 ans[i % ( m - 1 )] ( ans[i % ( m - 1 )] ans[i] ) % mod, ans[i] 0;}NTT( f, 1 );for( int i 0;i len;i ) f[i] f[i] * f[i] % mod;NTT( f, -1 );for( int i m - 1;i len;i ) f[i % ( m - 1 )] ( f[i % ( m - 1 )] f[i] ) % mod, f[i] 0;n 1;}printf( %lld\n, ans[fi[x]] );return 0;
}
