题解：P6300 悔改

· · 题解

题目描述

给定一些长度的木棍，两两组合，求可组成的长度组成数量的最大值和此时组成的长度。

思路

First

设 c_k 表示长度为 k 的有多少个，ans_k 表示答案是 k 时，数量的最大值。

显然答案即求 ans_k 的最大值。

容易想到 ans_k 的表示如下：

ans_k = \frac{1}{2} \sum_{i+j=k} \min(c_i,c_j)

（其中的 \frac{1}{2} 需要注意）

设 K 表示一共有多少个 c_i \ne 0，则时间复杂度为 O(K^2)。

这种方法适用于 K 较小的时候（或者说，所有的 c_i 都比较大的时候）。

Second

我们接着往下想。

发现 i+j=k 十分像卷积。

（废话，标签都告诉你了）

但是是对 \min(c_i,c_j) 求和，考虑枚举 \min(c_i,c_j)。

ans_k = \frac{1}{2} \sum_{i+j=k} \min(c_i,c_j)\\ = \frac{1}{2} \sum_{d=1}^{n} \sum_{i+j=k} [c_i \ge d][c_j \ge d]

然后发现：复杂度似乎变高了？

我知道你很急，但你先别急。

设 K 表示一共有多少个 c_i \ne 0，则时间复杂度是 O(Km \log m)。

Third

如果将以上两种合并呢（类似根号分治）？

不妨：当 i \ge s 时用法一，i \le s-1 时用法二。

则时间复杂度变成 O(sm \log m + \frac{n^2}{s^2})。

当 s m \log m = \frac{n^2}{s^2}，即 s= \sqrt[3]{ \frac{n^2}{m \log m} } 时时间复杂度最优。

不妨设 n，m 在同一数量级，则 s= \sqrt[3]{\frac{n}{ \log n}}，时间复杂度为 O((n^4 \log^2 n )^ \frac{1}{3} )。

Last

两部分有重复计算，减去即可。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0;ch=getchar();}
    while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return flag? x:-x;}
void write(int x,char ch=0){if(x<0) x=-x,putchar('-');
    static short s[35],top=-1;do{s[++top]=x%10;x/=10;}while(x);
    while(~top) putchar(s[top--]+48);if(ch) putchar(ch);}
int ksm(int a,int b,int p)
{
    int ans=1%p;
    while(b)
    {
        if(b&1)
        ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
const int N=1e6+5;
const int Max_Num=13;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3fll;
const int Base=3;
const int rBase=332748118;
int n,m;
int a[N];
int ans[N];

namespace NTT
{
    int A[N],rev[N];
    int limit,Li;
    void init()
    {
        limit=1,Li=0;
        while(limit<=m*2) limit<<=1,Li++;
        for(int i=0;i<limit;i++) rev[i]=((rev[i>>1]>>1)|((i&1)<<(Li-1)));
    }
    void Clear(int A[],int n){for(int i=0;i<n;i++) A[i]=0;}
    void solve(int F[],int t)
    {
        int i,j,mid;
        for(i=0;i<limit;i++)
        {
            if(i<rev[i])
            swap(F[i],F[rev[i]]);
        }

        for(mid=1;mid<limit;mid<<=1)
        {
            int step=ksm(t==1? Base:rBase,(mod-1)/(mid<<1),mod);
            for(i=0;i<limit;i+=(mid<<1))
            {
                int cur=1;
                for(j=0;j<mid;j++,cur=cur*step%mod)
                {
                    int x=F[i+j],y=cur*F[i+j+mid]%mod;
                    F[i+j]=(x+y)%mod;
                    F[i+j+mid]=(x-y+mod)%mod;
                }
            }
        }

        if(t==-1)
        {
            int inv=ksm(limit,mod-2,mod);
            for(i=0;i<limit;i++)
            F[i]=F[i]*inv%mod;
        }
    }
    void Just_Do_It(int k)
    {
        int i;
        Clear(A,limit);
        for(i=1;i<=m;i++) A[i]=(a[i]>=k);
        solve(A,1);
        for(i=0;i<limit;i++) A[i]=A[i]*A[i];
        solve(A,-1);
        for(i=0;i<limit;i++) ans[i]+=A[i];
    }
}

vector<int> Wzn;
signed main()
{
    int i;
    n=read(),m=read();
    for(i=1;i<=n;i++) a[read()]++;
    NTT::init();
    for(i=1;i<=Max_Num;i++) NTT::Just_Do_It(i);

    for(i=1;i<=m;i++)
    {
        if(a[i]>Max_Num)
        Wzn.push_back(i);
    }
    for(auto i:Wzn)
    {
        for(auto j:Wzn)
        ans[i+j]+=min(a[i],a[j])-Max_Num;
    }
    for(i=1;i<NTT::limit;i++) ans[i]/=2;

    int Ans[2]={0,INF};
    for(i=1;i<NTT::limit;i++)
    {
        if(Ans[0]<ans[i] || (Ans[0]==ans[i] && Ans[1]>i))
        Ans[0]=ans[i],Ans[1]=i;
    }
    write(Ans[0],' '),write(Ans[1],'\n');
    return 0;
}