「SCOI2014」方伯伯的商场之旅 解题报告

「SCOI2014」方伯伯的商场之旅

我一开始的想法会被两个相同的集合位置去重给搞死，不过应该还是可以写的，讨论起来老麻烦。

可以先钦定在\(1\)号点集合，然后往后调整一部分。

具体一点，通过前缀和减去后缀和的正负性移动

写的时候把\(sum\)压进去搞会非常简单

---

Code

#include <cstdio>
#include <cstring>
#define ll long long
ll dp[25][3000];int bit[25],k;
ll dfs(int dep,int sum,int limit)
{
    if(dep==0) return sum;
    if(!limit&&~dp[dep][sum]) return dp[dep][sum];
    ll ret=0;
    for(int i=0,up=limit?bit[dep]:k-1;i<=up;i++)
        ret+=dfs(dep-1,sum+(dep-1)*i,limit&i==up);
    return limit?ret:dp[dep][sum]=ret;
}
ll dfs(int dep,int pos,int sum,int limit)
{
    if(sum<0) return 0;
    if(dep==0) return sum;
    if(!limit&&~dp[dep][sum]) return dp[dep][sum];
    ll ret=0;
    for(int i=0,up=limit?bit[dep]:k-1;i<=up;i++)
        ret+=dfs(dep-1,pos,sum+(dep<pos?-1ll:1ll)*i,limit&i==up);
    return limit?ret:dp[dep][sum]=ret;
}
ll cal(ll x)
{
    int cnt=0;
    while(x)
    {
        bit[++cnt]=x%k;
        x/=k;
    }
    memset(dp,-1,sizeof dp);
    ll ret=dfs(cnt,0,1);
    for(int i=2;i<=cnt;i++)
        memset(dp,-1,sizeof dp),ret-=dfs(cnt,i,0,1);
    return ret;
}
int main()
{
    ll l,r;
    scanf("%lld%lld%d",&l,&r,&k);
    printf("%lld\n",cal(r)-cal(l-1));
    return 0;
}

---

2019.2.23