考虑容斥，通过$Bell(p)$的时间枚举所有等价情况。

对于一种情况，强制了一个等价类里面的数都要相同，其它的可以相同也可以不同。

这方案数显然可以通过多项式乘法求得，乘上容斥系数$(-1)^{p-等价类个数}\ \ \ \ \ \ \ \times(每个等价类大小-1)!之积$。

可以先把那$p$个多项式DFT，然后在点值表示下计算答案，最后再IDFT回来即可。

时间复杂度$O(pn(\log n+Bell(p)))$。

 

#include
     
      #include
      
       #include
       
        using namespace std;typedef long double ld;const int N=65540;const ld pi=acos(-1.0);int T,C,_,P,n,m,a[N],i,j,pos[N],w[6];struct comp{  ld r,i;  comp(ld _r=0,ld _i=0){r=_r,i=_i;}  comp operator+(const comp&x){return comp(r+x.r,i+x.i);}  comp operator-(const comp&x){return comp(r-x.r,i-x.i);}  comp operator*(const comp&x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}}f[6][N],g[N];inline void FFT(comp*a,int n,int t){  for(int i=1;i
        
         
          n)n=a[i];    }    n*=P;    for(m=1;m<=n;m<<=1);    j=__builtin_ctz(m)-1;    for(i=0;i
          
           >1]>>1|((i&1)<
           
            0.5)printf("%d: %.0f\n",i,(double)ans); } puts(""); } return 0;}