FFT优化背包

可以推出dp式子

乘法不可做。M是质数，变成原根

dp式子现在是加法

其实每次是原来的f数组，对可以转移的s集合进行卷积（即FFT优化背包）

直接快速幂搞定

 

详细一些：

循环卷积无非就是多了一个取值的位置，每次FFT之后，一个位置再变成两个位置的和，剩下>=m的位置再变成0

也有结合律

 

注意，S中有0，而0没有原根，并且x>=1所以选择0一定不是答案。直接pass掉

代码：

// luogu-judger-enable-o2#include
     
      #define reg register int#define il inline#define numb (ch^'0')#define int long longusing namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=8005*8;const int mod=1004535809;int n,m,o;int len;int G;int s[N],sz;ll ret[N];ll qm(ll x,ll y,int mo){    ll ret=1;    while(y){        if(y&1) ret=ret*x%mo;        x=x*x%mo;        y>>=1;    }    return ret;}ll f[N],h[N];int id[N];int rev[N];void fft(ll *f,int n,int c){    for(reg i=0;i
      
       >=1;    }}int main(){    rd(n);rd(m);rd(o);rd(sz);    int cnt=0;    int lp;    for(reg i=1;i<=sz;++i){        rd(lp);if(lp) s[++cnt]=lp;    }    findG();//    cout<<" GG "<
       
        <
        
         >1]>>1|((i&1)?len>>1:0);    }//    cout<<" len "<
         
          <