※ 引述《lubrige (lubrige)》之铭言：
: 题目: http://ppt.cc/Aogu
: 给予整数 N, R, Q，求一最大的正整数 M，使得
: (1) 将 N 和 M 写成十进制表示时，M 是 N 的 subsequence
: (2) M 除 Q 会余 R
: 其中 1 <= N < 10^1000, 0 <= R < Q <= 1000
: 目前的做法是
: 定义状态 f[i][j]，表示从 N 的最高位开始，考虑过前 i 个数字是否选进 M，且
: 余 j 的情况时 M 的最大长度 (暂不考虑 value 大小)，其中若为走不到的状态则填-1
: 转移为 (d(k) 为 k 从最高位下来第 k 个数字， zero base)
: / f[i - 1][j]
: f[i][j] = max |
: \ f[i - 1][j'] + 1, j = (10 * j' + d(i - 1)) % Q,
: if f[i - 1][j'] != 0 or d(i - 1) != 0
: boundary condition:
: 1. f[0][0] = 0
: 2. f[0][i] = -1, for 0 < i < Q
上面长度 f[i][j] 的计算是正确的，没有问题
: 最大长度的表填完之后，再从 N 的最低位做回来，并且另外开一张表 g[i][j]，
: 记到 f[i][j] 这格所形成的最长 subsequence，最高位数字是多少。
有点看不太懂 "f[i][j] 这格所形成的最长 subsequence" 是指哪一段 sequence
根据你的递回式，脑补 g[i][j] 的意思是(?):
选择 M 的第 f[i][j] 个数字 (zero base) 最大可行值是 g[i][j]
并且，这个值是从 d[i-1]~d[n-1] 选来的，
且 M 的前 i-1 个位模 Q 的余数是 j
: 对于不是 -1 的格子，取下面里比较大的数字 (这部份用 buttom up 来说)：
: 1. g[i + 1][j], if f[i + 1][j] == f[i][j]
: 2. d(i), if f[i + 1][j'] == f[i][j] + 1, j' = (10 * j + d(i)) % Q
在算出 g[i][j] 后，应该是要再从高位找下来?
那这边的找法，应该是从 i=j=0 开始，
如果 g[i][j] 这格是 case 1. 就 i++; 看下一格就好
如果是 case 2.， 输出 g[i][j]; j=(j*10+g[i][j])%Q; i++;
不知道原 po 的做法是不是这样? 如果是的话就要先判 case 2.
因为数字一样时先取走一定比较好，反过来虽然之后还是能拿到一样的数字
但可能会导至之后可以选的数字变小
例如 881 4 7 这个测资，算出 f[][], g[][] 应该是这样
f 0 1 2 3 4 5 6
0 0 * * * * * *
1 0 1 * * * * *
2 * 1 * * 2 * *
3 * * * * 2 * *
g 0 1 2 3 4 5 6
0 8 * * * * * *
1 8 8 * * * * *
2 * 1 * * X * *
g[0][0] 的 8 是来自 g[1][0] 或 d[0] (f[1][8%7]==f[0][0]+1, case 2.) 都行
不过这里要选 case 2. (i,j)=(0,0)=>(1,1)=>(2,4)=>(3,4)
8 8 X
选 case 1. 的话， (i,j)=(0,0)=>(1,0)=>(2,1)=>(3,4)
X 8 1
: 另外因为这部份倒过来做，所以为了避免抓到不是从 f[length(N)][R] 填回来的数字，
: 上面的计算还考虑是不是从 f[length(N)][R] 填回来的，如果不是的话一样不考虑
: g[i + 1][j] 或 d(i)，这部份再记一张来解决。
: 不过答案不对，想请问一下有没有什么没有考虑到地方，先谢谢大家 0w0/

抱歉 g[i][j] 那段写得不好 不过我们想的应该是同一件事就是在 dag 上找字典序最大或最小那样然后两个 case 都存在且平手的话也是抓 case 2 没问题最后再从最高位输出回来 我觉得应该是哪边写烂了不过一直看不太出来 QwQ

方便给source code吗XD 我想看一下

f 的第 0 个 column 似乎是整排的 0? 虽然应该是不影响

嗯对，我标*的位置从g[|N|][R]走回来走不到的点

http://codepad.org/VwCMbCgU 对不起这样麻烦 见笑了 QwQ

第73行的p[i][j][1]有可能是坏的 (如果case 2没有成功)要先检查 p[i][j] 有没有填过 (p[i][j][0]==rnd_cnt)没有的话，不用比p[i][j][1],p[i+1][j][1]，直接做74行if(p[i][j][0]!=rnd_cnt || p[i][j][1]<p[i + 1][j][1])(line 74)p[i][j][0] = rnd_cnt;

嗯嗯 感谢帮忙 不过还没有想透什么情况下这句会出包我直觉上令为 -1 应该可以避掉 case 2 的失败可是这样看起来结果并不是这样

我也不太清楚XD 不过我测 1101 1 6 你会印 11 这样可能要 trace 一下发生什么事

啊啊 似乎是因为我把 back tracking 的 pointer 也放在line 74 里面 这样在 case 2 失败 而且 i + 1 到 L之间都没有选数字的话 会因为同为 -1 使 p[i][j][3]没有被正确的 assign 到 最后在印答案的时候余数就乱跳实际上应该是要 re 的 因为 p[i][j][3] 在这种情况下都会是 -1 XDD这笔测资太重要了 非常感谢 0 w0b