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中的所有元素。
1<=N<=10^9，3<=M<=8000，M為質數
0<=x<=M-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]$：表示選了$i$個數的乘積$\%m=j$的方案數
$$f[i<<1][j]=\sum _{(j_1\times j_2)\%m=j}f[i][j_1]\times f[i][j_2]$$
乘法目前來說是超越知識
那么將相乘轉化為指數上的相加，暴艸出$m$的原根
題目保證了$m$是質數，一定會有原根
$$f[i<<1][j]=\sum _{(j_1+j_2)\%m=j}f[i][j_1]\times f[i][j_2]$$
這就長得很像可以卷積的玩意兒
涉及取模那就用$NTT$
但是這個跟普通的式子下面的條件略有不同$j_1+j_2=j$
$[m?1,2m?2]$這里面也會對答案有貢獻，被$m?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后應該都是一樣的 對最后%m=x的答案可能會有貢獻 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; }

總結

以上是生活随笔為你收集整理的[SDOI2015]序列统计 （NTT）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。