返回信息流http://eeach.site/static/images/target.png
猿辅导笔试第三题，想过用三维dp，但是没找出递推公式，求大佬解惑。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #98295同步于 2019/9/3
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
猿辅导笔试题，感觉像是DP仿佛又找不出递推公式
eeach
2019/9/3镜像同步12 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
F[x][y] 表示还剩y次改写的情况下，有x位相同的情况。
初始 F[t][M]=1 ,t是一开始两个串相同的位数
L是两个串的长度,C(n,m)是n个中选m的组合数
F[t][M]=1
for y=M downto 1
for x=0 to L
for i=max(0,x+K-L) to min(x,K)
for j=0 to K-i
F[X-i+j][y-1]+=F[x][y]*2^{i}*C(x,i)*C(L-x,K-i)*C(K-i,j)
print F[L][0]
组合数预处理一下，过程注意及时取模，时间复杂度O(n^4)
给个思路呀！dfs超时了吧
【 在 Wizmann (Wizmann) 的大作中提到: 】
: dp[Step][Hash]
: 二维就够吧。Step是修改的次数，Hash是字符串的Hash值。
: ...................
膜拜大佬，还在啃你的思路
【 在 JSZKC (JSZKC) 的大作中提到: 】
: F[x][y] 表示还剩y次改写的情况下，有x位相同的情况。
: 初始 F[t][M]=1 ,t是一开始两个串相同的位数
: L是两个串的长度,C(n,m)是n个中选m的组合数
: ...................