集训队作业赖thesis

1、密码系统浅析IOI 2010 中国国家集训队命题答辩活动杭州二中 赖陆航题意简述输入整数N, B, M, V将所有模M为V的N位B进制数，按照各数位构成的集合分类，求每一类数各有多少个（记为Ans）答案模10007样例说明10032223926100311131223210322139131721251:0, 1:0, 1, 2:1, 2:N=3B=3M=4V=13位的3进制数模4为1Ans0, 1=1Ans0, 1, 2=1Ans1=1Ans1, 2=2其他集合的Ans=0极限数据范围位数N:2, 109基数B:2, 10模M:1, 40余数V:0, M)解题思路DPn, s, m: 长度为

2、n，数位集合为s，模M为m的B进制数（首位可以为0）的数目（模10007）DPn, s, m=sum DPn, s, m | d0, , B-1, n+1=n, sd=s, Bm+dm(mod M) 长度为n，数位集合为s，模M为m后一位d长度为n+1，数位集合为sd，模M为(Bm+d) mod M动态规划！O(2BNM)解题思路N最高可达109需要包含logN复杂度倍增/快速幂解题思路长度为n1，数位集合为s1，模M为m1(n2, s2, m2)长度为n1+n2，数位集合为s1s2，模M为(Bn2m1+m2) mod MDPn, s, m=sum DPn1, s1, m1 DPn2, s2,

3、 m2 | s1s2=s, Bn2m1+m2m(mod M) (n1+n2=n)依次求出DP1,*,*, DP2,*,*, DP4,*,*, 用N的二进制展开可以合并得到DPN,*,*转移函数快速幂O(2BM)2logN)类似快速幂的倍增方法解题思路复杂度中2B很大，如何去除？将数位集合的限制从状态移到转移d0, , B-1(n, s, m)ds(n, m)但这会求出AnsS=sum AnsT | T包含于S 容斥原理！解题算法枚举0, , B-1的子集S动态规划dS以转移函数快速幂优化得到AnsS容斥原理，从Ans求出Ans数据生成与分数分布编号算法复杂度期望得分1搜索O(BN)102朴素动

4、态规划O(2BNM)303以矩阵快速幂优化的状态压缩动态规划O(8BM3logN)504以转移函数快速幂优化的状态压缩动态规划O(4BM2logN)705以矩阵快速幂优化的动态规划+容斥原理O(2BM3logN+3B)706以转移函数快速幂优化的动态规划+容斥原理O(2BM2logN+3B)100列出可能的解法，分配期望得分数据生成与分数分布测试数据NBMV接受算法12随机整数2, 10311随机整数0, M)1, 2, 3, 4, 5, 636随机整数2, 1032, 3, 4, 5, 6710随机整数2, 1093, 4, 5, 6111084, 61214110151065, 616187192862031根据期望得分设计测试数据总结朴素的动态规划加速转移：转移函数快速幂减少状态：容斥原理完美解决此题考查动态规划优化为动态规划加速提供新方向谢谢！转移函数初始状态ddd转移函数一些状态的DP值转移后状态的DP值提炼转移特征值：长度n，数位集合s，模m转移函数由二元组(n, T)决定它将DP映射到DP，满足DPn1+n, s, m=sum DPn1, s1, m1 Ts2, m2 | s1s2=s, Bnm1+m2m(mod M) 。转移函数若f, g分别由(n1, T1)和(n2, T2)决定，则fg由 (n, T)决定，满足n=n1+n2, Ts, m=sum Ts1,