UVA 12297 – Super Poker

据说是湖南省赛最难的题。。。

首先围观这个题目,先枚举相同卡片出现次数的组合,

比如 1,1,2 就是2个1,1个2,就是(1,2)

1,1,1,5,5,6,6,4 就是(1,2,2,3)

有了这个组合之后,比如是C=(1,2,2,3),

我们就要求出 x+2y+2z+3e = N 且x,y,z,e都不同的解,注意y和z的顺序是无关紧要的,所以还要除2!

那么令F(V)表示(X dot V) = N且X中元素都不同的X个数

考虑如何计算F(V),令G(V) = (X dot V) = N的X个数,

这是经典问题可以使用生成函数计算

那么G(V) = Sum(F(V’)) V’是V的一种组内元素相同的方式

那么就能解出F(V)了

懒得写的更详细了,意识流一下吧

7 thoughts on “UVA 12297 – Super Poker

  1. super poker 那题是枚举pattern(同样的牌选几张)然后把多项式乘积用等比数列求和公式转化为简单的多项式相乘然后容斥计算出满足解不同这个条件的解数……?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>