3771: Triple

2024-03-27 04:48

文章标签 triple 3771

本文主要是介绍3771: Triple，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考虑三个多项式 $a \ b \ c$
令 $a$ 表示选取一个相同的方案数
令 $b$ 表示选取两个相同的方案数
令 $c$ 表示选取三个相同的方案数
取一个的方案数即 $a$
取两个的方案数即 $\frac{a^2-b}{2}$
考虑实际上 $a^2-b$ 算得是排列数，所以需要除以 $2$
同理可推出三个的方案数即 $\begin{align*} & \ \ \ \ \frac{a^3 - 3*(a*b - c) - c}{6}\\ &= \frac{a^3 - 3*a*b + 2*c}{6} \end{align*}$
c++ 代码如下：

#include<bits/stdc++.h>
#define PI acos(-1)
#define rep(i,x,y) for(register int i = x ;i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ;i >= y; -- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{char c;int sign = 1;x = 0;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}struct cpx
{double x, y;cpx(){}cpx(double a,double b){ x = a,y = b; }cpx operator * (int a) { return cpx(x * a,y * a); }cpx operator / (int a) { return cpx(x / a,y / a); }cpx operator + (cpx a) { return cpx(x + a.x,y + a.y); }cpx operator - (cpx a) { return cpx(x - a.x,y - a.y); }cpx operator * (cpx a) { return cpx(x*a.x-y*a.y,x*a.y+y*a.x); }cpx operator *=(cpx a) { *this = *this * a; }
};const int N = 2e5 + 50;
int R[N],L,n,m,mx;
cpx a[N],b[N],c[N],ans[N];inline void fft(cpx*a,int f)
{rep(i,0,n-1) if(i < R[i]) swap(a[i],a[R[i]]);for(register int i = 1; i < n ; i <<= 1){cpx nw = cpx(cos(PI/i),f * sin(PI/i));for(register int j = 0; j <  n ; j += i << 1){cpx w = cpx(1,0); for(register int k = 0; k < i ; ++k,w *= nw){cpx x = a[j + k],y = w * a[i + j + k];a[j + k] = x + y;a[i + j + k] = x - y;}}}if(f == -1) rep(i,0,n-1) a[i].x /= n;
}int main()
{read(n);rep(i,1,n){int x;read(x);mx = max(mx,x);a[ x ].x = 1;b[x*2].x = 1;c[x*3].x = 1;}m = mx * 3;for(n = 1;n <= m; n <<= 1) ++ L;rep(i,0,n) R[i] = ((R[i>>1])>>1)|((i&1)<<(L-1));fft(a,1); fft(b,1); fft(c,1);rep(i,0,n - 1) ans[i] = a[i] + (a[i]*a[i] - b[i])/2 + (a[i]*a[i]*a[i] - a[i]*b[i]*3 + c[i]*2)/6;fft(ans,-1);rep(i,0,n) if(int(ans[i].x+0.5)) printf("%d %d\n",i,int(ans[i].x+0.5));return 0;
}