专栏文章

题解：AT_abc392_g [ABC392G] Fine Triplets

OOneLeft
AT_abc392_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq9ejp6
此快照首次捕获于
2025/12/04 01:06
3 个月前
此快照最后确认于
2025/12/04 01:06
3 个月前
查看原文

题意

给你一个大小为 NN 的集合 SS，求满足 A<B<CA<B<C 且 B−A=C−BB-A=C-B 且 A,B,C∈SA,B,C\in S 的三元组 (A,B,C)(A,B,C) 个数。

思路

设集合中某个数 xx 出现的次数为 cntxcnt_x，考虑枚举 BB 和 B−AB-A，则答案为：
∑i=1n∑j=1sicntsi−jcntsi+j\sum_{i=1}^n\sum_{j=1}^{s_i}cnt_{s_i-j}cnt_{s_i+j}
其中 i=Ai=A，j=B−Aj=B-A。
设 fx=∑i=1xcntx−icntx+if_x=\sum_{i=1}^xcnt_{x-i}cnt_{x+i}，则原式可以转化为
∑i=1nfsi\sum_{i=1}^nf_{s_i}
我们规定 cnt0=0cnt_0=0，然后考虑化简 fxf_x，有
fx=∑i=1x−1cnticnt2x−i=(∑i=0xcnticnt2x−i)−cntx2=∑i=02xcnticnt2x−i2−cntx2\begin{aligned} f_x&=\sum_{i=1}^{x-1}cnt_icnt_{2x-i}\\ &=\left(\sum_{i=0}^xcnt_icnt_{2x-i}\right)-cnt_x^2\\ &=\frac{\sum_{i=0}^{2x}cnt_icnt_{2x-i}}{2}-cnt_x^2 \end{aligned}
不难发现 ∑i=02xcnticnt2x−i\sum_{i=0}^{2x}cnt_icnt_{2x-i} 是一个卷积的形式，带入原式得
(12∑i=1n∑j=02aicntjcnt2ai−j)−n\left(\frac{1}{2}\sum_{i=1}^n\sum_{j=0}^{2a_i}cnt_jcnt_{2a_i-j}\right)-n
因为任意一个在集合中出现的元素 xx 都有 cntx=1cnt_x=1，故 cntx2=1cnt_x^2=1，所以最终算出来再统一减去 nn 即可。
设 f(x)=∑i=0106xicntxf(x)=\sum_{i=0}^{10^6}x^icnt_x，g(x)=∑i=0106xicntxg(x)=\sum_{i=0}^{10^6}x^icnt_x，计算出 f∗gf*g 的系数再统计答案即可。这里使用NTT来达到 O(nlog⁡n)O(n\log n) 的时间复杂度。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5,mod=998244353,g=3;//998244353=(2^23)*7*17
int fpow(int n,int k=mod-2)//快速幂
{
    int res=1,base=n;
    for(;k>0;k>>=1)
    {
        if((k&1)==1)res=1ll*res*base%mod;
        base=1ll*base*base%mod;
    }
    return res;
}
const int invg=fpow(g);
int rev[N<<2];
void NTT(int*a,int len,bool inv) //NTT
{
    for(int i=0;i<len;i++)
        if(i<rev[i])swap(a[i],a[rev[i]]);
    for(int mid=1;mid<len;mid<<=1)
    {
        int wn=fpow(inv?invg:g,(mod-1)/(mid<<1));
        for(int i=0;i<len;i+=mid<<1)
        {
            int wk=1;
            for(int j=i;j<i+mid;j++,wk=1ll*wk*wn%mod)
            {
                int x=a[j],y=1ll*wk*a[j+mid]%mod;
                a[j]=(x+y)%mod,a[j+mid]=(x-y+mod)%mod;
            }
        }
    }
}
void times(int n,int m,int*a,int*b) //计算多项式相乘的系数
{
    int len=1,cnt=0;
    while(len<=n+m)len<<=1,cnt++;
    for(int i=1;i<len;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<cnt-1);
    NTT(a,len,false),NTT(b,len,false);
    for(int i=0;i<len;i++)a[i]=1ll*a[i]*b[i]%mod;
    NTT(a,len,true);
    for(int i=0;i<len;i++)a[i]=1ll*a[i]*fpow(len)%mod;
}
int a[N<<2],b[N<<2],x[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i],a[x[i]]++,b[x[i]]++;
    times(1e6,1e6,a,b);
    ll ans=0;
    for(int i=1;i<=n;i++)ans+=a[2*x[i]]; //统计答案
    cout<<(ans-n)/2;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...