[ABC362E] Count Arithmetic Subsequences 题解

Po7ed · 2024-08-08 12:59:41 · 题解

[ABC362E] Count Arithmetic Subsequences

看到其他题解写的都是 dp，所以交一个数学优化爆搜的题解。

题意

给出一个长度为 n 的序列 a，对于 1\le l\le n 求长度为 l 的等差子序列数量 ans_l。

以下用 d 表示公差，l 表示子序列长度。

爆搜

注意到 n\le 80 的数据范围，非常诡异，考虑爆搜。我们充分发扬人类智慧，可以发现随机数据下答案是比较小的，也就是说等差子序列并不多。

于是可以写出如下爆搜代码：

#include <iostream>
#include <map>
// #include <random>

using std::cin;
typedef long long ll;
constexpr int N=100;
ll a[N];
int n;

ll ans[N]; // ans[i] 表示长度为 i 的等差子序列个数
// i 表示当前搜到 a[i]，l 记录长度，d 代表公差
inline void dfs(int i,int l,ll d)
{
    ans[l]++; // 累加答案
    for(int j=i+1;j<=n;j++)if(a[j]-a[i]==d)
    { // 搜后继
        dfs(j,l+1,d);
    }
}


std::map<std::pair<int,ll>,bool> vis; // 防止重复搜
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // std::mt19937 rnd(114514);
    // for(int i=1;i<=80;i++)printf("%d ",rnd()%114);
    // return 0;
    // 赛时用来造随机数据测试
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    { // 枚举头两个数
        for(int j=i+1;j<=n;j++)if(!vis[{i,a[j]-a[i]}])
        { // 只搜没搜过的
            vis[{i,a[j]-a[i]}]=true;
            dfs(i,1,a[j]-a[i]);
        }
    }
    ans[1]=n; // 保险起见
    for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
    return 0;
}

结果 T 了两个手造数据。

优化

考虑如果我们是出题人，该怎么卡。可以发现如果 \forall 1\le i\le n,\,a_i=1（即数据全为 1），任意子序列都是 d=0 的等差序列，此时长度为 l 的答案为 \dbinom{n}{l}，答案之和为 2^n，直接爆炸。

考虑让爆搜避开它不擅长的领域，只搜 d\ne 0 的等差子序列。d=0 的情况用数学优化。具体的，设 cnt_x 表示 a 中 x 的出现次数，则 d=0 时

注意 d=0 的情况对 ans_l 有贡献，但贡献不是直接等于 ans_l，因为还有其他情况。

代码

#include <iostream>
#include <map>
// #include <random>

using std::cin;
typedef long long ll;
constexpr int N=100,mod=998244353;
ll a[N];
int n;

ll ans[N];
void dfs(int i,int l,ll d) // 爆搜
{
    ans[l]++;
    for(int j=i+1;j<=n;j++)if(a[j]-a[i]==d)
    {
        dfs(j,l+1,d);
    }
}

ll qpow(ll x,ll y) // 快速幂，用来求逆元
{
    ll res=1;
    while(y)
    {
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
ll fac[N]; // 阶乘
ll C(int n,int m) // 组合数
{
    return fac[n]*qpow(fac[m],mod-2)%mod*qpow(fac[n-m],mod-2)%mod;
}

std::map<ll,bool> vis;
std::map<ll,int> cnt;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // std::mt19937 rnd(114514);
    // for(int i=1;i<=80;i++)printf("%d ",i);
    // return 0;
    cin>>n;
    fac[0]=1;
    for(int i=1;i<=n;i++)cin>>a[i],fac[i]=fac[i-1]*i%mod,cnt[a[i]]++;
    for(int i=1;i<=n;i++)
    { // 枚举头两个数
        for(int j=i+1;j<=n;j++)if(!vis[a[j]-a[i]]&&(a[i]-a[j])) // 必须满足 d=a[i]-a[j]!=0
        {
            vis[a[j]-a[i]]=true;
            dfs(i,1,a[j]-a[i]);
        }
        vis.clear(); // 判重方法和上面略有不同（其实等价）
    }
    for(auto x:cnt) // 对于每个数，这里 x.first 为值，x.second 为出现次数
    {
        for(int l=1;l<=x.second;l++)
        {
            ans[l]=(ans[l]+C(x.second,l))%mod; // 加上 d=0 的贡献
        }
    }
    ans[1]=n; // 保险起见
    for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
    return 0;
}

AC 记录。目前排在洛谷最优解第 4，前面 3 位好像也是类似方法。