首页 > 其他 > 详细

整除问题(对问题描述的分析)(即对dp状态的分析)

时间:2017-09-24 13:29:52      阅读:30      评论:0      收藏:0      [点我收藏+]

标签:如何   但是   范围   mes   ren   输出   -c   data-   情况   

整除问题

问题描述:
给定N个正整数,和一个数M,要求从这N个数中选出一些数来求和,使和为M的整数倍,问一共有多少种方法。
0≤M,N≤1000
输入:
第一行两个数表示N和M;
第二行N个数 分别表示给定的这N个数。
输出:
一个整数,表示方法总数对1234567的余数
不考滤N个数中的相同数引起的重复。
例如
3 2
2 2 4
可以有{2},{2},{4},{2,4},{2,4},{2,2},{2,2,4} 共7种方法。

既然是选出一些数,那么就是背包问题,但是他又不大像背包问题,所以我们需要从头看起(O_O)?

预备知识,余数性质

1. 整数除法中被除数未被除尽部分,且余数的取值范围为0到除数之间(不包括除数)的整数。例如27除以6, 商数为4,余数为3。

2.一个数除以另一个数,要是比另一个数小的话,商为0,余数就是它自己.。例如:1除以2,商数为0,余数为1。2除以3,商数为0,余数为2。

3.取余数运算:a % b = c 表示 整数a除以整数b所得余数为c。

余数的计算公式:c = a -⌊ a/b⌋ * b其中,⌊ ⌋为向下取整运算符,向下取整运算称为Floor,用数学符号⌊ ⌋表示

例:⌊ 3.476 ⌋=3,⌊6.7546⌋=6,⌊-3.14159⌋= -4

如 7 mod 3 = 7-⌊7/3⌋*3=7-2*3=1

4.余数和除数的差的绝对值要小于除数的绝对值(适用于实数域)这不是废话吗QWQ

5.被除数=除数×商+余数;

除数=(被除数-余数)÷商;

商=(被除数-余数)÷ 除数;

余数=被除数-除数×商。

(这都是废话)

6.如果a,b除以c的余数相同,那么a与b的差能被c整除。例如,17与11除以3的余数都是2,所以17-11能被3整除。

7.a与b的和除以c的余数(a、b两数除以c在没有余数的情况下除外),等于a,b分别除以c的余数之和(或这个和除以c的余数)。例如,23,16除以5的余数分别是3和1,所以(23+16)除以5的余数等于3+1=4。注意:当余数之和大于除数时,所求余数等于余数之和再除以c的余数。例如,23,19除以5的余数分别是3和4,所以(23+19)除以5的余数等于(3+4)除以5的余数。

8.a与b的乘积除以c的余数,等于a,b分别除以c的余数之积(或这个积除以c的余数)。例如,23,16除以5的余数分别是3和1,所以(23×16)除以5的余数等于3×1=3。注意:当余数之积大于除数时,所求余数等于余数之积再除以c的余数。例如,23,19除以5的余数分别是3和4,所以(23×19)除以5的余数等于(3×4)除以5的余数。

好了,哔哔了这么久,需要一个看法了
从最简单的开始,设dp(i)表示前i个数,构成%m==0的方案数(注意,是m的整数倍就是%m==0)(信息学中,许多数学知识都需要往%上靠)
思考第i个数,如果不选择第i个数,则dp(i)=dp(i-1)
如果选择第i个数,等等,我们需要知道 我们需要知道前i个数的具体情况因为,我们只知道前i个数有一些方案%m==0,但是,我们不知道如何选择i。
所以这个状态自然而然的扩展到了二维来描述问题
设dp(i,j)表示前i个数选一些数,%m==j的方案数
按照原来的dp(i,j)=dp(i-1,j)+dp(i-1,k)
因为我们要维护dp(i,j)表示前i组成的方案,那么他还可继承i-1个数中,满足(k+num[i])%m==j的情况,但是这是余数方程,有点难解

有两种处理方法1.将(k+num[i])%m==j变为(k%m+num[i]%m)%m==j直至可解

还有一种方法,既然dp(i,j)可以通过dp(i-1,k)k满足(k+num[i])%m==j的情况继承

那么如果dp(i,j)如果已经算出了,他可以使什么被继承呢dp(i+1,j)还有dp(i+1,(j+num[i+1])%m==j)

这样的话,我们依然可以用已知去填未知把问题缩小,只是从被动变成主动了

这样的话,在不改变循环顺序的情况下,就可以出解。

如下附上代码n(*≧▽≦*)n

附:这道题,我们可以看出,dp写转移方程时有几个重要的思想:1.维护,2.继承。如果不满足,就只能换状态喽。

 

整除问题(对问题描述的分析)(即对dp状态的分析)

标签:如何   但是   范围   mes   ren   输出   -c   data-   情况   

原文:http://www.cnblogs.com/star-eternal/p/7586814.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号