自动搬运

查看原文

来自洛谷，原作者为

	hsfzLZH1 我永远喜欢珂朵莉

搬运于2025-08-24 22:07:26，当前版本为作者最后更新于2019-01-10 20:21:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给出 $n,k$ ， 求 $\sum_{i=1}^n f(i,k)$ 的值， $f(i,k)$ 定义为将十进制整数 $i$ 表示为 $k$ 进制时写成一个数列的形式中的最长子串为等差数列的长度。答案取模 $19260821$ 。

10pts $1≤n≤10^6,k=60$

枚举 $1...n$ 的所有值。对于每个数，用 $O(\log_{k}n)$ 的时间复杂度将这个整数分解为 $k$ 进制数。然后，计算出它的最长连续等差数列的长度。如何计算最长子串为等差数列的长度呢？

首先，如果这个 $k$ 进制数的长度大于二，那么答案至少为二（因为任意两个整数都可以组成合法的长度为二的等差数列），我们考虑使用 $O(\log_k n)$ 的时间复杂度的方法求解本问题。从前到后扫一遍，如果这一项减上一项的值等于上一项减上上一项的值，那么根据等差数列的定义，其仍然能成为一个等差数列，长度为原来加一。如果不等于，那么就要找到一个新的等差数列，不妨设这个新的等差数列的前两项就为当前项和上一项，这样就能求出最优解。时间复杂度为 $O(k\times \log_kn)$ 。

10pts $k=10$

观察到 $k$ 的值比较小，所以可能的等差数列有两种情况：

1.等差数列的公差为 $0$ ，可以 $O(\log_{k}n)$ 预处理；

2.等差数列的公差不为 $0$ ，这时等差数列的长度最多为 $k$ ，然后……出题人自己也不会做了。

40pts $2\le k\le 20,0\le l\le r\le k^{10}$

得到这 $40$ 分的同学大部分可能都使用的是数位DP，可能是递推式不够完美，存储了冗余信息，没有最优化记忆化等问题，没有得到满分。

100pts

** 数位DP ** 。这题的形式就是数位DP的标准形式，而且非常直白，甚至连差分的套路都没有了。

考虑在转移的过程中计算 $5$ 个参数，当前计算剩余的位数 $x$ ， 已知的前缀的最长等差数列的长度记为 $lgt$ ，以当前计算的值为结尾的最长等差数列的长度记为 $nww$ ，上一位的值 $ls$ ，上上一位的值 $lls$ 。在转移的过程中，利用在第一个得分点得出的结论，利用递推的形式判断能否形成更长的等差数列，并更新 $nww$ 和 $lgt$ 的取值。由于上面几个参数的渐进多项式分别为 $O(\log_k n)$ ， $O(\log_k n)$ ，$O(\log_k n)$ ，$O(k)$ ，$O(k)$ ，所以最后的时间复杂度是 $O(k^2\log_{k}^3 n)$ 。空间复杂度也相同。正好能卡在空间限制和时间限制内。

代码展示

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxk=61;
const int maxn=19;
const int maxl=110;
typedef long long ll;
const int mod=19260821;
ll k,l,n[maxl],r;
int f[maxn][maxn][maxn][maxk][maxk];
char s[maxl];
inline void upd(int&x,int v){x+=v;while(x>=mod)x-=mod;}
vector<int>dim;
int dfs(int x,int lgt,int nww,int lls,int ls,bool op)
{
    if(!x)return max(lgt,nww);
    if(!op&&~f[x][lgt][nww][lls][ls])return f[x][lgt][nww][lls][ls];
    int maxx=op?dim[x]:(k-1),ret=0;
    for(int i=0;i<=maxx;i++)
    {
        if(lls==k&&ls==k)
        {
            if(i)upd(ret,dfs(x-1,1,1,k,i,op&(i==maxx)));
            else upd(ret,dfs(x-1,0,0,k,k,op&(i==maxx)));
        }
        else if(lls==k)upd(ret,dfs(x-1,2,2,ls,i,op&(i==maxx)));
        else if(ls-lls==i-ls)upd(ret,dfs(x-1,max(lgt,nww+1),nww+1,ls,i,op&(i==maxx)));
        else upd(ret,dfs(x-1,lgt,2,ls,i,op&(i==maxx)));
    }
    return f[x][lgt][nww][lls][ls]=ret;
}
int main()
{
    memset(f,-1,sizeof f);
    scanf("%s%lld",s,&k);
    l=strlen(s);
    for(int i=0;i<l;i++)n[i]=s[l-i-1]-'0';
    dim.push_back(-1);
    while(l)
    {
    	r=0;
    	for(int i=l-1;i>=0;i--)
    	{
    		int t=r;
    		r=(r*10+n[i])%k;
    		n[i]=(t*10+n[i])/k;
        }
        while(l&&!n[l-1])l--;
        dim.push_back(r);
    }
    printf("%d\n",dfs(dim.size()-1,0,0,k,k,true));
    return 0;
}

闲言碎语

19260821不是质数

$19260821=23\times 193\times 4339$