题解 SP1433 【KPSUM - The Sum】

#### $Upd$ $on$ $2020.4.28:$ 发现还有一种思路$,$就加上去了$.$ 数位$DP.$ 这个题有两种思路$:$ 一种是枚举交错和然后求出每种交错和的数的个数$,$并且还要考虑奇偶性$,$比较繁琐$.$ ~~pcf写这个写了~~ $6$ ~~维状态(逃~~ 另一种是直接把这些数作为一个整体来$dp$交错和$.$ 记$dpsum(presum,prelen,n,1/0)$表示已经确定的前缀的交错和为$presum$ $,$已经确定的前缀**排除掉前导零**的长度为$prelen,$还有$n$位没有确定$,$目前的位数中是$/$否有非零数 的交错和$.$ 为了$dp$这个数值$,$我们还需要知道$dplen(prelen,n,1/0)$表示已经已经确定的前缀**排除掉前导零**的长度为 $prelen$ $,$ 还有$n$位没有确定$,$目前的位数中是 $/$ 否有非零数 的数字的长度总和$.$ 注意到$len/prelen$本身并不重要$,$只和奇偶性有关$,$所以$dp$过程中的$len/prelen$可以对 $2$ 取模 $,$ 可以进一步压缩状态$.$ 复杂度$O(S*m*10),$其中$S$为最大的交错和的绝对值$,$ $m$为最大位数$.$ 处理一次询问的复杂度为 $O(m*10).$ 代码$:$ ```cpp #include <bits/stdc++.h> #define LL long long using namespace std; LL n,pw[18]; inline void init(){ int i; for (pw[0] = i = 1; i < 18; ++i) pw[i] = pw[i-1] * 10; } inline LL DPsum(int presum,int prelen,int n,int tp); inline int DPlen(int prelen,int n,int tp); inline int getf(LL l){ return l % 2 == 1 ? 1 : -1; } LL Ans,Len; inline void work(){ int i,j,x,presum = 0,prelen = 0,v; bool flag = 0; Ans = Len = 0; for (i = 15; i >= 0; --i) if (flag || (x = n/pw[i]%10)){ x = n/pw[i]%10; for (j = 0; j < x; ++j){ v = (j||prelen||flag)?1:0; Ans += getf(Len+1) * DPsum(presum+j*getf(prelen+v),(prelen+v)%2,i,v); Len += DPlen(prelen+v,i,v); Len %= 2; } ++prelen; presum += getf(prelen)*x; flag = 1; prelen%=2; } cout << Ans << '\n'; } int main(){ init(); cin >> n; while (n) ++n,work(),cin >> n; return 0; } int dplen[2][16][2]; bool vislen[2][16][2]; inline int DPlen(int prelen,int n,int tp){ if (prelen < 0 || n < 0) return 0; prelen%=2; if (n == 0) return prelen * tp; if (vislen[prelen][n][tp]) return dplen[prelen][n][tp]; vislen[prelen][n][tp] = 1; if (tp) dplen[prelen][n][tp] = DPlen(prelen+1,n-1,1); else dplen[prelen][n][tp] = DPlen(prelen,n-1,0); dplen[prelen][n][tp] += 9 * DPlen(prelen+1,n-1,1); dplen[prelen][n][tp] %= 2; return dplen[prelen][n][tp]; } LL dpsum[80*2][2][16][2]; bool viss[80*2][2][16][2]; inline int pos(int s){ return s + 80; } inline LL DPsum(int presum,int prelen,int n,int tp){ if (prelen < 0 || n < 0) return 0; if (n == 0) return tp * presum; if (viss[pos(presum)][prelen][n][tp]) return dpsum[pos(presum)][prelen][n][tp]; viss[pos(presum)][prelen][n][tp] = 1; LL tot = 0,Len = 0; int i,v; for (i = 0; i <= 9; ++i){ v = (i||prelen||tp)?1:0; tot += getf(Len+1) * DPsum(presum+i*getf(prelen+v),(prelen+v)%2,n-1,v); Len += DPlen(prelen+v,n-1,v); Len %= 2; } return dpsum[pos(presum)][prelen][n][tp] = tot; } ```