Luogu P2119 [NOIP 2016 普及组] 魔法阵 题解 [ 绿 ] [ 枚举 ] [ 数学 ] [ 前缀和 ]

魔法阵：数学推导加暴力统计。

注意到 \(m\) 比 \(n\) 大，于是先把所有数装进值域为 \([1,n]\) 的桶里。

首先这两个式子显然不太好做，于是先来推一波式子：

\[\begin{equation}\begin{aligned}b-a&<\frac{c-b}{3}\\4b-3a&<c\\b+3(b-a)&<c\end{aligned}\end{equation} \]

因为 \(b-a=2(d-c)\)，于是考虑枚举 \(b-a\) 的值，这样 \(d-c\) 的值也能确定了。

接下来就是容易的了，考虑继续枚举 \(b\)，进而能直接求出 \(a\) 的值与 \(c\) 的下界，而当 \(d-c\) 为定值且 \(c\) 要满足大于某个值的情况是好做的，直接在确定 \(d-c\) 之后跑后缀和即可。由此就可以在枚举 \(b\) 后快速统计 \(a,b\) 的方案数，乘法原理乘起来即可。

\(c,d\) 的方案数也是同理，此处不再赘述。

时间复杂度 \(O(n^2)\)，实际跑不满。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
const int N=40005,V=15005;
int n,m,a[N],tot[V],ansa[N],ansb[N],ansc[N],ansd[N],pre[V],suf[V];
void solve(int cz)
{
    int hcz=cz/2;
    memset(pre,0,sizeof(pre));
    memset(suf,0,sizeof(suf));
    for(int i=1;i<=n;i++)
    {
        pre[i]=pre[i-1];
        if(i-cz>0)pre[i]+=tot[i]*tot[i-cz];
    }
    for(int c=n;c>=1;c--)
    {
        int mxb=c-3*cz-1;
        if(mxb<=0)break;
        if(c+hcz<=n&&tot[c]&&tot[c+hcz])
        {
            ansc[c]+=pre[mxb]*tot[c+hcz];
            ansd[c+hcz]+=pre[mxb]*tot[c];
        }
    }
    for(int i=n;i>=1;i--)
    {
        suf[i]=suf[i+1];
        if(i+hcz<=n)suf[i]+=tot[i]*tot[i+hcz];
    }
    for(int b=1;b<=n;b++)
    {
        int mnc=b+3*cz+1;
        if(mnc>n)break;
        if(b-cz>=1&&tot[b]&&tot[b-cz])
        {
            ansa[b-cz]+=suf[mnc]*tot[b];
            ansb[b]+=suf[mnc]*tot[b-cz];
        }
    }
}
int main()
{
    //freopen("sample.in","r",stdin);
    //freopen("sample.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i];
        tot[a[i]]++;
    }
    for(int cz=2;cz<=n;cz+=2)solve(cz);
    for(int i=1;i<=m;i++)
        cout<<ansa[a[i]]<<" "<<ansb[a[i]]<<" "<<ansc[a[i]]<<" "<<ansd[a[i]]<<'\n';
    return 0;
}