[ABC322G] Two Kinds of Base 题解

· · 题解

前言

没人写题解，研究了好久，来总结一下。正巧还没做过这种套路。

正文

0x00 题目分析

转化一下题目变成，给定了 N,x 两个正整数，定义一个函数 F\left(a,b,S\right)，有：

F\left(a,b,S\right)=\sum_{i=0}^{k-1}S_i\times\left(a^{i}-b^{i}\right)

其中 a,b 是两个正整数，满足 a,b\le N,a\gt b；S 是一个下标 0 起、元素个数为 k 的数组，满足 S_{k-1}\not=0 且 0\leq S_{i}\lt\min\left(a,b,10\right)。现在求对于 a,b,S 使得 F\left(a,b,S\right)=x。

发现这玩意很像是一个特殊进制的数，不妨把 i=0,1,\cdots,k-1 依次看做这个数的低位到高位，有一下性质符合和一个进制很像：

  1. 随着 S 的长度增长，F 函数增长是指数级别的，即当 S 的长度为 k 时，F\left(a,b,S\right) 函数是 \mathcal{O}\left(a^k\right) 的。

  2. 对于任意满足题目条件的 S，若 x\gt0，有 F\left(a,b,S\right)\lt x\times\left(a^{k}-b^{k}\right)。就像是进制填数一样，高位填的数一定是决定性的，后面永远追不上，证明显然拆开 \left(a^{i}-b^{i}\right) 这一坨即可。

0x01 开始解题

根据第一条性质可得，对于任意会成为答案的 k，其级别是 \mathcal{O}\left(\log x\right)；根据第二条性质得，对于每一对确定的 a,b,k 若存在解，只有唯一的 S 能满足要求。

不妨考虑暴力枚举 a,k 两个数，然后确定一个 b。那么对于一个 b，有一个基本的要求是 a^{k-1}-b^{k-1}\leq x 不然最高位只能填 0，但是不能有前导 0，理性分析一下这个要求 b^{k-1}\geq a^{k-1}-x 则，b 下界是 \mathcal{O}\left(a-\Delta\right) 的，而且 \Delta 上界是 \mathcal{O}\left(x^{\frac{1}{k-1}}\right)，并且 b\le a 反正这玩意小得很就对了，b 取值范围大小肯定不超过根号。

这里枚举一下满足这些条件的 a,b,k 就可以了最多枚举 \mathcal{O}\left(n\sqrt{x}\right)。接下来就是随便像是填一个其他进制的数一样把 x 填进去，看能不能填下就可以了。

0x02 完了吗？

注意对于 k=2 情况要特殊处理，由于 i=0 时 a^{i}-b^{i} 是 0，那么可以乱填；当 i=1 时算出 \left(a-b\right)\times S=x 的方案数即可。

其他情况，同样由于 i=0 时 a^{i}-b^{i} 是 0 所以可以乱填，贡献答案有个系数注意计算。

最终时间复杂度 \mathcal{O}\left(n\sqrt{x}\log^2 x\right)，很多时候跑不满，常数很小。

0x03 代码实现

注意所谓乱填 S_0 也不是乱填，要满足那几条条件。

AC CODE

#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){register char s[20];register int i=0;if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return;}while(x){s[i++]=x%10;x/=10;}while(i){putchar(s[--i]+'0');}return;}

long long pw[200010][23];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("name.in", "r", stdin);
    freopen("name.out", "w", stdout);
    #endif

    register int i,k;
    register long long a,b,S;
    const long long mod=998244353;
    register long long res=0,tmp,now;
    long long n=read();
    long long x=read();

    //k=2
    for(S=1;S<=std::min(x,9ll);++S)
        if(!(x%S)){
            for(a=S+1+(x/S);a<=n;++a){//b<10
                b=a-x/S;
                if(b>=10) break;
                (res+=b)%=mod;
            }
            if(n-(x/S)>=10) (res+=10*(n-((x/S)+10)+1))%=mod;//b>=10   a in [x/S+10,n] , b in [10,...]
        }

    //otherwise
    for(a=1;a<=x;++a) pw[a][2]=a;
    for(k=3;k<=22;++k){
        for(a=1;a<=std::min(x-1,n);++a){
            tmp=1;
            for(i=1;i<k&&tmp<=(1e13);++i) tmp*=a;
            if(tmp>(1e13)) break;
            pw[a][k]=tmp;//pw[a][k] = a^(k-1) , f = pw[a][k]*S1+pw[a][k-1]*S2 ...
            for(b=a-1;b;--b){
                //check
                if(pw[a][k]-pw[b][k]>x) break;
                now=x;
                for(i=k;i>1;--i)//S{k-i+1} = now mod pw[a][i]-pw[b][i]
                    if(now/(pw[a][i]-pw[b][i])>=std::min(10ll,b)) goto loop;
                    else now%=pw[a][i]-pw[b][i];
                if(now) goto loop;
                (res+=std::min(10ll,b))%=mod;
                loop:;
            }
        }
    }

    print(res);

    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}

总结

抓住题目中这个东西“进制”这样的性质解题，熟悉套路。

p.s. 本文可能有笔误，看不懂得可以问我。