題目

設(shè)有\(A\)種顏色顏色出現(xiàn)了奇數(shù)次，出現(xiàn)的次數(shù)總和為\(B\)；那么就有\(D-A\)種顏色出現(xiàn)偶數(shù)次，出現(xiàn)的次數(shù)總和為\(n-B\)。那么就能裝\(\frac{B-A}{2}+\frac{n-B}{2}=\frac{n-A}{2}\)個(gè)瓶子。如果要至少裝滿\(m\)個(gè)瓶子，就有\(\frac{n-A}{2}\geq m\)，即\(A\leq n-2m\)。

于是能否裝滿\(m\)個(gè)瓶子只和有多少種顏色出現(xiàn)奇數(shù)次有關(guān)，不難搞一個(gè)dp，設(shè)\(dp_{i,j}\)表示前\(i\)個(gè)珍珠，有\(j\)種出現(xiàn)了奇數(shù)次的方案數(shù)；轉(zhuǎn)移的話枚舉一下第\(i+1\)顆珍珠是出現(xiàn)了奇數(shù)次的顏色還是出現(xiàn)了偶數(shù)次的顏色，乘上顏色數(shù)直接轉(zhuǎn)移即可。復(fù)雜度是\(O(nD)\)的。

這樣我們的dp也就做到頭了，考慮容斥一波，設(shè)\(g_i\)表示至少有\(i\)種顏色的珍珠出現(xiàn)了奇數(shù)次，設(shè)\(F(x)=\displaystyle \sum_{i\geq 0}\frac{x^{2i+1}}{(2i+1)!}\)即出現(xiàn)次數(shù)為奇數(shù)次的珍珠的生成函數(shù)。那么就有\(g_i=n![n]\binom{D}{i}F^{i}(x)e^{x(D-i)}\)，即從\(D\)種顏色里選\(i\)種出現(xiàn)奇數(shù)次，對(duì)于剩下的\(D-i\)種顏色出現(xiàn)次數(shù)隨意。

不難發(fā)現(xiàn)\(F'(x)=\displaystyle \sum_{i\geq 0}\frac{x^{2i}(2i+1)}{(2i+1)!}=\displaystyle \sum_{i\geq 0}\frac{x^{2i}}{(2i)!}\)，那么顯然有\(F(x)+F'(x)=e^x\)。再進(jìn)一步發(fā)現(xiàn)\(F''(x)=F(x)\)。利用這兩條性質(zhì)構(gòu)造一下\(F(x)\)，發(fā)現(xiàn)\(F(x)=\frac{e^x-e^{-x}}{2}\)。

于是有

不難發(fā)現(xiàn)這是一個(gè)卷積的形式，直接ntt求出\(g\)即可。求出\(g\)之后再做一個(gè)二項(xiàng)式反演就能直接算答案了。

代碼。