nowcoder 8996 A

题目

https://ac.nowcoder.com/acm/contest/8996/A

大意

n 由8个整数成分组成

1. 不超过1
2. 不超过2
3. 不超过3
4. 偶数个
5. 奇数个
6. 4的倍数
7. 不超过1
8. 3的倍数

题解

1. 打打表找规律直接得到公式

2. 生成函数

$(1+x)(1+x+x^2)(1+x+x^2+x^3)(\frac{1}{1-x^2})(\frac{x}{1-x^2})(\frac{1}{1-x^4})(1+x)(\frac{1}{1-x^3}) = \frac{x}{(1-x)^4}$

$=x(1+x+x^2+x^3…)^4$

只需要$x^N$的系数即可