因为如果一位小朋友得不到糖果，那么在她身后的小朋友们也都得不到糖果。

所以设g[i][j] 表示前i位小朋友，分到j个糖果，且前i位小朋友都分到糖果的方案数

令F(x) 表示分到x个糖果的欢乐程度

∴g[i][j] = ∑ g[i-1][j-k]*F(k)

记g[i]=g[i-1]*F，则 g[i]=F ^ i

但是要求的是 Σ g[i][m]

记f[n]=Σ g[i]  i∈[1,n] ，那么ans=f[n][m]

f[n]=Σ g[i]  i∈[1,n]

     =Σ f(n/2)+Σ g[i]  i∈[n/2+1,n]

     =Σ f(n/2)+Σ F^i  i∈[n/2+1,n]

     =Σ f(n/2)+Σ F^(n/2+i)  i∈[1,n/2]

     =Σ f(n/2)+F^(n/2) * Σ F^i  i∈[1,n/2]

     =Σ f(n/2)+g(n/2)*f(n/2)

然后可以分治解决

如果n是奇数，f(n)=f(n-1)+g[n]=f(n-1)+g(n-1)*f

边界条件：g[][0]=1

 

#include
     
      #include
      
       #include
       
        using namespace std;const int M=1<<17;#define N 10001int m,mod;int r[M+1];int len;const double pi=acos(-1);struct Complex{    double x,y;    Complex() { }    Complex(double x_,double y_):x(x_),y(y_) { }    Complex operator + (Complex p)    {        Complex C;        C.x=x+p.x;        C.y=y+p.y;        return C;    }    Complex operator - (Complex p)    {        Complex C;        C.x=x-p.x;        C.y=y-p.y;        return C;    }    Complex operator * (Complex p)    {        Complex C;        C.x=x*p.x-y*p.y;            C.y=x*p.y+y*p.x;        return C;    }    void clear()    {        x=y=0;    }};typedef Complex E;E F[M+1],f[M+1],g[M+1],tmp[M+1];void FFT(E *a,int ty){    for(int i=0;i
        
         >1]>>1)|((i&1)<