题目大意

也懒得解释题目大意了……

正解

正解居然是\(FFT\)？

不要看题目的那个式子这么长，也不要在那个式子上下手。

其实我们会发现，不同的\((x_i-x_j,y_i-y_j,z_i-z_j)\)并不多。

如果我们求出每个三元组的出现次数，后面的就好做了。

那怎么求呢？

祭出我们的大杀器——\(FFT\)。

考虑只有一个维怎么做。设两个多项式分别为\(A\)和\(B\)。

对于\(x_i\)，就在\(A\)的\(x_i\)这一位上的系数加一；

对于\(x_j\)，就在\(B\)的\(77-x_j\)这一位上的系数加一。

将\(A\)和\(B\)乘起来，那么\(77+x_i-x_j\)就是差\(x_i-x_j\)对应的个数。

对于三维，就将这三个数压成一维的就好了。

实际上也可以用NTT。仔细分析一下，就可以发现每个三元组的出现次数肯定是不超过\(998244353\)的。

正解

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define N 1000000#define MX 3652264#define mo 998244353inline int input(){    char ch=getchar();    while (ch<'0' || '9'
         
          >=1,x=(long long)x*x%mo) if (y&1) res=(long long)res*x%mo; return res;}inline int pow4(int x){x*=x;return x*x;}#define M (1<<22)#define bit 22int n;struct DOT{ int x,y,z; inline DOT rev(){return {77-x,77-y,77-z};}} d[N];inline int pia(const DOT &a){return (a.x*154+a.y)*154+a.z;}int a[1<<22],b[1<<22],cnt[1<<22];int rev[1<<22];inline void ntt(int *a,int flag){ for (int i=0;i
          
           =mo?x+y-mo:x+y); a[k+i]=(x-y<0?x-y+mo:x-y); } } } if (flag==-1){ int invm=my_pow(M,mo-2); for (int i=0;i
           
            >1]>>1|(i&1)<