题解 P5128 【好时光】

· · 题解

题目大意

给出 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