UOJ Logo NaCl的博客

博客

363 水题题解

2019-02-12 20:16:57 By NaCl

前排接受高一 julao 光环照耀

明明 363 才是最水的…

非常显然的数位 DP,记录两个状态:⑴当前位置;⑵当前异或和。

此时我们发现询问不同的数,可以共用 DP 到的值,因为状态转移与询问的数无关。(否则会 TLE)

#include <cstdio>
#include <cstring>
#include <ctime>
const int KB = 100001;
const int MOD = 1000000007;

char n[KB]; int ca[KB][45]; // n - 读入的数,ca - 存 DP 值
// 因为询问数长度不同,ca 数组只能正着存
// 即 ca[KB - 1] 对应个位,ca[KB - 2] 对应十位…
// 因此下面查询需要一个 nr 代表这一位置

int ss(int cr, int nr, bool lim, int o) {
// cr - 当前位置,nr - 对应 DP 值位置,lim - 是否设限,o - 当前异或和
  int de, cn = n[cr] - '0', re = 0; de = lim? cn: 9;
  if(!n[cr]) return o; if(!lim && ~ca[nr][o]) return ca[nr][o];
  for(int i = 0; i <= de; ++i)
    re = (re + ss(cr + 1, nr + 1, lim && i == cn, o ^ i)) % MOD;
  return lim? re: (ca[nr][o] = re); }

int dp() { scanf("%s", n); return ss(0, KB - strlen(n), 1, 0); }

int main() {
  int t; memset(ca, -1, sizeof ca); scanf("%d", &t); while(t--) {
    int a = dp(), lv = 0, rs; for(int i = 0; n[i]; ++i) lv ^= n[i] - '0';
// 我们用 (从 1 到 N) - (从 1 到 M) 得到 (从 M + 1 到 N)
// 而题目问 (从 M 到 N),故应将 M 的值(lv)加上去
    rs = dp() + lv + MOD - a; printf("%d\n", rs >= MOD? rs - MOD: rs); }
  return 0; }

换言之,也可直接预处理 DP 值

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。