我们可有用DP很快地求出用x个数字构成y的方案数
1 | f[i][j]=f[i-1][m-a[k]] |
其中a()为数字集合S中的数。
主要难点在于题目中条件3:前后和相等或奇偶和相等。考虑容斥。
我们可以很快地求出前后和相等+奇偶和相等的方案数,再减去既是前后和相等又是奇偶和相等的方案数即可。
我们已知用x个数字构成y的方案数,如何快速求前后和相等的方案数?
前后和相等时,这个数字可以表示为【 A 】【 B 】,由两端长度为n的数字构成,且他们的和相等。
首先显然要枚举前后和,假设为i。则A有f(n,i)种取法,B也有f(n,i)种取法,因此前后和相等且为i的方案数为$sqr(f(n,i))$
对于所有的前后和,答案为$\sum sqr(f[n][i])$
如何快速求奇偶和相等的方案数?
脑补把上文的A和B的每个数字穿插。新构成的数就是A1B1A2B2A3B3…AnBn,这时新构成的数奇偶和相等。
因此方案数和前后和相等的方案数相等,为$\sum sqr(f[n][i])$
如何快速求奇偶和相等且前后和相等的方案数?
考虑一个数x我们可以把它分成【A】【B】前后长度各位n的两部分,记A0为A中偶数位的和,A1为A中奇数位的和,B0为B中偶数位的和,B1为B中奇数位的和。
要使得前后和相等且奇偶和相等,则
1 | A0+A1=B0+B1 |
解得
1 | A0=B1 |
分别求出A0=B1 A1=B0的对数,相乘即为答案。
下文中A0 A1 B0 B1分别表示处于这些位置的数字的个数,而非处于这些位置的数字的和
如果n是偶数,例如n=4
位数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
奇偶 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
属于 | A1 | A0 | A1 | A0 | B1 | B0 | B1 | B0 |
A0=2 A1=2 B0=2 B1=2
重复答案:$\sum (f[A0][i]·f[B1][i])·\sum (f[A1][i]·f[B0][i])=\sum (f[2][i]·f[2][i])·\sum (f[2][i]·f[2][i])$
如果n是奇数,例如n=5
位数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
奇偶 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
属于 | A1 | A0 | A1 | A0 | A1 | B0 | B1 | B0 | B1 | B0 |
A0=2 A1=3 B0=3 B1=2
重复答案:$\sum ( f[A0][i] · f[B1][i] ) · \sum ( f[A1][i] · f[B0][i] ) = \sum ( f[2][i] · f[2][i] ) · \sum ( f[3][i] · f[3][i] )$
可以发现$A0=B1<=A1=B0$
设$t1=A0=B1,t2=A1=B0$,则重复的答案为$\sum sqr(f[t1][i]) · \sum sqr(f[t2][i])$
容斥一下,最终答案为
$2·\sum sqr(f[n][i])-\sum sqr(f[t1][i]) · \sum sqr(f[t2][i])$
code
1 |
|