带有计数色彩课件.pptxVIP

带有计数色彩的DP其实我也不知道到底该取啥名字就这么取了

Hyperrectangle求一个l1,l2,…,ld的超立方体，被超平面x1+x2+…+xd=s截的体积。每一维边长为不超过300的整数。d=300

Solution如果只有x1+x2+…+xd=s，那么体积为s^d/d!考虑每一维不满足为xi=li，容斥即可。dp[i][l]表示考虑了前i维，不满足的和为l的总系数。

FoxJumping从(0,0)点一路跳到(N,M)点,并且跳正好R次。每次跳跃的(i,j)-(i+x,j+y)满足x=n,y=m，并且不能原地不动。同时我们有一些ai，要满足x,y不都等于ai,同时ai都是10的倍数。N,M=800,n,m=800,R=1600.ai的个数小于等于50.

Solution有一个主要的条件就是不能跳任何一个(ai,ai)。考虑容斥就是R步里面有多少步跳了(ai,ai)。注意到这里有用的只有跳的个数和ai的和。所以我们先考虑乱走，这个时候x与y是独立的，所以可以分别求出r[p][q]表示走p步，和为q的方案和c[p][q]。接着我们计算一下dp[p][q]表示走了p步不合法的，然后长度总和为10q的方案。接着根据步数容斥即可。

SRM526给你一个字符串集合X等几率从字符串集合中挑出K个字符串(可以重复)并拼成一个大字符串?问S在大字符串中的期望出现次数?|S|?500;|X|?50;|X_i|?50;K10^12

SHOI2009舞会N个男生N个女生，各自都有身高。我们要将他们配成N对，使得不超过K对男的比女的高。N=200需要高精度

首先我们枚举一个男生的集合，这些男生都高于他的舞伴。具体的做法可以使用dp,从低到高考虑每个人，dp[i][j]表示前i个男生选了j个方案。对于剩下的人可以随便乱连，也就是dp[n][j]*(n-j)!也就是求出了有k个人，使得男生比女生高的方案f(k)。然后算出恰好k个男生比女生高的方案。时间复杂度O(n^2)

TopCoderSRM684600ptsDivFree一个长度为n的序列，满足每个元素都是[1,k]内的整数，且对于相邻的两个元素a=Si,b=Si+1，有a=b或amodb≠0。求这样的序列的个数模1000000007。n,k=50000.

agc005DMythologicalsama喜欢排列。因为她不喜欢整数K，她的排列会满足以下条件。对于一个排列$a_1,a_2,\cdots,a_N$,对于任意的$1\leqi\leqn$,$|a_i-i|\not=K$请问有多少长度为$N$的排列满足以上条件？请输出答案对$924844033$(一个质数)取模的答案$n\leq2000$

Heromeetdevil给你一个只由AGCT组成的字符串S(|S|=15)，对于每个0=i=|S|，问有多少个只由AGCT组成的长度为m(1=m=1000)的字符串T，使得LCS(S,T)=i？

考虑原来的LCS动态规划f(i,j)发现f(i,j)-f(i,j-1)∈{0,1},所以我们可以把f(i)差分后装压起来，就能做了。