有好多好玩的知识点

题意：在集合中选$ n$个元素(可重复选)使得乘积模$ m$为$ x$，求方案数对$ 1004535809$取模

$ n<=10^9，m<=8000且是质数，集合大小不超过m$

---

$ Solution:$

我们先考虑改乘积为加和之后怎么做

直接对于集合中的数构建生成函数

所要求的就是这个生成函数的$ n$次幂的所有模$ m$为$ c$的项的系数的和

用快速幂优化这个生成函数的$ n$次幂

每次乘法之后立刻把$ [m,2m)$的系数加回$[0,m)$

这样可以保证每时每刻生成函数的长度不超过$ m$

就可以直接$ NTT$优化这个过程了

时间复杂度为$ O(m log m log n)$

 

然后考虑乘积的情况

我们知道$ x^ax^b=x^{a+b}$

尝试把每个数改成某个底数的若干次方

由于$ m$是质数一定存在原根

原根有性质是它的$[0,phi(m))$在模$ m$意义下互不相同

这样就可以直接把每个集合中的数改成$ m$的原根的若干次方就好了

然后就是加和情况的做法

复杂度不变

注意可能要特判原集合中存在$ 0$的情况

---

 $ my \ code$

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define p 1004535809#define rt register int#define ll long longusing namespace std;inline ll read(){ ll x = 0; char zf = 1; char ch = getchar(); while (ch != '-' && !isdigit(ch)) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf;}void write(ll y){ if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}void writeln(const ll y){write(y);putchar('\n');}int i,j,k,m,n,x,y,z,cnt,c,yg;int a[100010],val[8555];namespace NTT{ int ksm(int x,int y){ int ans=1; for(rt i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*x*ans%p; return ans; } vector
             
              R; void NTT(int n,vector
              
               &A,int fla){ A.resize(n); for(rt i=0;i
               
                R[i])swap(A[i],A[R[i]]); for(rt i=1;i
                
                 <<=1){ int w=ksm(3,(p-1)/2/i); for(rt j=0;j
                 
                  <<1){ int K=1; for(rt k=0;k
                  

&A){ NTT(n,A,1); for(rt i=0;i