数位dp [SCOI2014]方伯伯的商场之旅

https://www.luogu.org/problemnew/show/P3286

我当时在考场上的时候考虑两边的数位dp
但是要处理是否有\(limit\) 非常的麻烦
然后就续了好久没有续出来

后来看到一个很棒的做法
就是刚开始的时候钦点一个汇集点\(1\)算出答案
然后考虑移动汇集点减少的答案
也就是说如果在汇集点右边贡献为正 左边的话贡献为负
数位dp两边就行了
复杂度\(O(len ^ 2 sum K)\)

#include<bits/stdc++.h>
#define int long long
#define fo(i, n) for(int i = 1; i <= (n); i ++)
#define out(x) cerr << #x << " = " << x << "\n"
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); ++ it)
using namespace std;
// by piano
template<typename tp> inline void read(tp &x) {
  x = 0;char c = getchar(); bool f = 0;
  for(; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
  for(; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
  if(f) x = -x;
}
template<typename tp> inline void arr(tp *a, int n) {
  for(int i = 1; i <= n; i ++)
    cout << a[i] << " ";
  puts("");
}

int f[233][2333], L, R, K;
int a_cnt = 0, a[2333];
int res = 0;

inline int dfs(int pos, int sum, int lim) {
  if(!pos) return sum;
  if(!lim && f[pos][sum] != -1) return f[pos][sum];
  int res = 0, up = (lim ? a[pos] : K - 1);
  for(int i = 0; i <= up; i ++) {
    res += dfs(pos - 1, sum + abs(1 - pos) * i, lim && (i == up));
  }
  if(!lim) f[pos][sum] = res;
  return res;
}
int now = 0;
inline int fr(int pos, int sum, int lim) {
  if(sum < 0) return 0;
  if(!pos) return sum;
  if(!lim && f[pos][sum] != -1) return f[pos][sum];
  int res = 0, up = (lim ? a[pos] : K - 1);
  for(int i = 0; i <= up; i ++) 
    res += fr(pos - 1, sum + (pos >= now ? i : -i) , lim && (i == up));
  if(!lim) f[pos][sum] = res;
  return res;
}

inline int doit(int n) {
  if(n == 0) return 0;
  memset(f, -1, sizeof f);
  a_cnt = 0;
  for(; n; a[++ a_cnt] = n % K, n /= K);
  res = dfs(a_cnt, 0, 1);
  for(int i = 2; i <= a_cnt; i ++) {
    now = i;
    memset(f, -1, sizeof f);
    res -= fr(a_cnt, 0, 1);
  }
  return res;
}

main(void) {
  read(L); read(R); read(K);
  cout << doit(R) - doit(L - 1) << "\n";
}