题解：AT_abc322_g [ABC322G] Two Kinds of Base

ABC322G

前言

MnZn第一次出题解。

题目描述

有个序列 S=(S_1,S_2,S_3,…,S_n)。
定义函数 f(S,a)=\sum\limits_{i=1}^{k}S_i \cdot a^{k-i}。
给定 N,X，求所有满足 F(S,a,b)=X 的三元组数量。

做法

定义 F(S,a,b) 的结果为 ans，ans=\sum\limits_{i=1}^{k}S_i \times(a^{k-i}-b^{k-i})。
对于 a^{k}-b^{k}，可以化成 (a-b)\sum\limits_{i=0}^{k-1}a^{k-i-1}b^{i} 的形式，因此可以发现：(a-b)|ans。
不难发现 ans 是关于 k 指数级增长的，故 k 的范围不会很大，小于 18。

证明如下：
定义 ans_i 为 k=i 时的结果，令 sum_i=\sum\limits_{j=1}^{i}(a-b)\times s_i \times b^{j-i}。
易发现 ans_i=a \times ans_{i-1}-sum_i。

因为本题的 k 的数据范围不大，因此可以分类讨论 k 的范围。

• k=2 的情况：

  可以考虑固定 S_1。在此之下，要满足 a-b=\frac {X}{S_1}。对于 a,b,S_2 要满足：

  • S_1 < b
  • a\leq N
  • S_2\leq \min(9,a,b)

  对于每一个 b，a 是唯一确定的，因此只需要对所有的 b 枚举并求和 \min(10,b)，其中 S_1 < b \leq N-\frac{X}{S_1}，可以在 O(1) 的复杂度确定。

• k \geq 3 的情况：

  由于 S_1 \neq 0，这代表 a^{k-1}-b^{k-1} \leq X。满足此条件的二元组 (a,b)，有 620787 组。
  前面已证 a^{k-i}-b^{k-i}\equiv 0\pmod{a-b}，此时令 s=a-b，由于需要 a^2-b^2 \leq X，把 s=a-b 代入得 s^2-2bs \leq X。 因此有 X\log X 数量级的组合情况。
  求解组合 (a,b)，最先想到的是动规，把计算 S 的方案当作背包问题，每一件物品的代价为 a^{k-i}-b^{k-i}。
  但枚举背包状态的复杂度是不能接受的，因此需要优化。
  事实上满足条件的 S 最多只有一个。

  证明如下：
  对于所有 k\geq 1，有 a^{k}-b^{k}>(b-1)\sum\limits_{i=0}^{k-1}a^i-b^i，该式可用归纳法证明。
  因此在求答案时只能贪心地从 S 中减去 a^k-b^k，故 S 是唯一的，且存在性可以在 O(\log X) 的时间内确定。

  因此在 k\geq3 的情况可以在 O(X\log^2X) 的时间内解决。又因 k 很小，且满足条件的 (a,b) 较少，因此复杂度是可以接受的。

因此该问题是由 k=2 和 k\geq 3 的情况加起来，总复杂度在 O(X\log^2X) 级别。

Code

#include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N=2e5+5,mod=998244353;
int n;
ll ans=0,x;
inline ll ksm(int x,ll y) {
    ll ret=1;
    while(y) {/*这里不能取模，此时是求a^k-b^k是否符合要求，若取模了会使答案不正确*/
        if(y&1) {
            ret=ret*x;
        }
        x=x*x;
        y>>=1;
    }
    return ret;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>x;
    for(int s=1; s<=sqrt(x); s++) {/*k=2的情况*/
        if(x%s) continue;
        if(s<10) {
            for(int a=s+1+(x/s); a<=n; a++) {
                int b=a-(x/s);
                if(b>=10) break;
                ans=(ans+b)%mod;
            }
            if(n-(x/s)>=10) ans=(ans+10*(n-(x/s)-9)%mod)%mod;
        }
        if(s*s!=x&&x/s<10) {
            for(int a=x/s+s+1; a<=n; a++) {
                int b=a-s;
                if(b>=10) break;
                ans=(ans+b)%mod;
            }
            if(n-s>=10) ans=(ans+10*(n-s-9)%mod)%mod;
        }
    }
    for(int k=3; k<=18; k++) {/*枚举k>2*/
        for(int a=1; a<=n; a++) {
            if(ksm(a,k-1)-ksm(a-1,k-1)>x) break;
            for(int s=1; s<a; s++) {
                int b=a-s;
                if(ksm(a,k-1)-ksm(b,k-1)>x) break;
                int v=x,flag=1;
                for(int i=1; i<k; i++) {
                    int noww=ksm(a,k-i)-ksm(b,k-i);
                    if(v/noww>=min(10ll,min(a,b))) {
                        flag=0;
                        break;
                    }
                    v=(v%noww);
                }
                if(flag&&!v) ans=(ans+min(10ll,min(a,b)))%mod;
            }
        }
    }
    cout<<ans;
    return 0;
}