Ryan_<

Dedicate to my great beloved mother.

直播爆零>_>

岁月不饶人，请亦千万不要饶过岁月:)

最近比赛中遇到的dp题目总结

POJ2480 longge's problem

1、\(当m与n互质时，(gcd(i,m*n)=gcd(i,m)*gcd(i,n)，则gcd为积性函数\)

因为积性函数的和也为积性函数，令所求函数

$\sum_{i=1}^n\sum_{d=1}^i\sum_{t=1}^(i/d)F(d)G(t,i)$

POJ3373 Candy Distribution

序列\(a[i]=(1+i)*i/2\);是否存在一个i，使得a[1]~a[i]对N取模的值恰好覆盖0~N。

<==>序列\(A[i]=(1+i)*i/2%N\);是否存在一个i，使得A[1]~A[i]构成模N的完全剩余系。

集合A是模N的完全剩余系的充要条件：

1)A中含有N个整数

2)A中任意两个整数对N不同余

<==>是否存在两个整数x、y，使得A[x]=A[y].

<==>是否存在两个整数x、y，使\((1+x)*x/2==(1+y)*y/2 (mod N)\)

<==>\((x-y)*(x+y+1)==0 (mod N)\)

x-y与x+y+1奇偶性不同，故：

N为奇数时,上述同余式一定成立,无法构成完全剩余系

N为2的幂次时,一定不成立,构成完全剩余系

其它情况：设\(N=S*2^e.(其中S为>1奇数，e>0)\)

构造法（构造出满足一个条件的情况，判断是否满足另一个条件）+分析法证明存在性

\(存在i,j<=N,满足(x-y)*(x+y+1)==0(mod N).\)

\(使上式满足条件,令x-y=S,x+y+1=2^(e+1)\)

\(解得x=1/2*(2^(e+1)-1+S),y=1/2*(2^(e+1)-1-S);\)

\(是否保证i,j<=N?\)

\(证明1/2*(2^(e+1)+1+S)<=S*2^e\)

\(即证2^(e+1)-1+S<=2^ (e+1)*S\)

\(即证2^(e+1)>=1\)

得证.

故此时无法构成N的完全剩余系.

POJ3244 Difference between Triplets

POJ3910

\(对于一个封闭集合S = {x1, x2, ..., xn},xi的因数d均在集合中,则有下面行列式的值: \)

\(=∏(1<=i<=n)φ(xi) \)

矩阵，矩阵！