bgm
你写题像CXK
因为要求没有那样的一堆人在闻鸡起舞,所以可以考虑容斥,枚举一定有(i)堆人在闻鸡起舞,然后其他位置随便放,容斥系数为((-1)^i).然后注意到因为一堆人一定是依次唱,跳,rap,篮球的,这些人出现的位置没有交,如果设(f_i)为随便放(i)人的方案,那么有(i)堆人在闻鸡起舞的方案就是(inom{n-3i}{i}f_{n-4i}),那个组合数就是枚举那些在闻鸡起舞的人的出现位置,可以看做在(n-3i)个位置中选出(i)个位置,然后在每个被选的位置后插(3)人
后面那个(f_{n-4i})显然可以用指数型生成函数算,也就是((n-4i)(sum_{j=0}^{b-j}frac{x^j}{j!})(sum_{j=0}^{c-j}frac{x^j}{j!})(sum_{j=0}^{d-j}frac{x^j}{j!})),暴力卷积就好了qwq
代码律师函警告