洛谷鏈接

顯然顏色數量不會超過 $\lim =\min (m,\frac{n}{s})$

$f_i:$ 至少有 $i$ 種顏色恰好出現了 $s$ 次的方案數。

則 $f_i=\left(\genfrac{}{}{0ex}{}{m}{i}\right)?\frac{n!}{(s!{)}^i(n?is)!}?(m?i{)}^{n?is}$。

$m$ 種顏色中選 $i$ 種，$\left(\genfrac{}{}{0ex}{}{m}{i}\right)$。

將 $n$ 個位置分成 $i+1$ 個部分，欽定的 $i$ 種顏色每種出現 $s$ 次，剩下 $m?i$ 種顏色共 $n?is$ 個。

先當作是可重的全排列，即 $\frac{n!}{\underset{i}{s!s!...s!}(n?is)!}$。

前 $i$ 各部分都是只有一種顏色，后面部分每個有 $m?i$ 種取法，所以要乘上 $(m?i{)}^{n?is}$。

$an{s}_i:$ 恰有 $i$ 個顏色出現恰好 $s$ 次的方案數。

直接二項式反演：$an{s}_i={\sum }_{j=i}^{\lim }(?1{)}^{j?i}(\genfrac{}{}{0ex}{}{j}{i})f_j$。
$$an{s}_i=\sum _{j=i}^{\lim }(?1{)}^{j?i}(\genfrac{}{}{0ex}{}{j}{i})f_j=\sum _{j=i}^{\lim }(?1{)}^{j?1}\frac{j!}{i!(j?i)!}{f}_j?an{s}_i?i!=\sum _{j=i}^{\lim }\frac{(?1{)}^{j?i}}{(j?i)!}j!?f_j$$
令 $F_i=i!?f_i,G_i=\frac{(?1{)}^i}{i!}$，則 $an{s}_i=\frac{1}{i!}{\sum }_{j=i}^{\lim }{G}_{j?i}{F}_j=\frac{1}{i!}{\sum }_{j=0}^{\lim ?i}{G}_j{F}_{j+i}$。

反轉 $F$，即 $F_i=(\lim ?i)!?f_{\lim ?i}$，則 $an{s}_i=\frac{1}{i!}{\sum }_{j=0}^{\lim ?i}{G}_j{F}_{\lim ?i?j}$。

可以卷了 $G?F$，$\text{NTT}$ 做即可。

#include <bits/stdc++.h> using namespace std; #define int long long #define mod 1004535809 #define maxn 10000005 #define maxm 500000 int fac[maxn], inv[maxn], r[maxm], W[maxm], f[maxm], g[maxm]; int len;int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }void NTT( int *c, int op ) {for( int i = 0;i < len;i ++ ) if( i < r[i] ) swap( c[i], c[r[i]] );for( int i = 1;i < len;i <<= 1 ) {int omega = qkpow( op == 1 ? 3 : mod / 3 + 1, (mod - 1) / (i << 1) );for( int j = 0;j < len;j += (i << 1) )for( int k = 0, w = 1;k < i;k ++, w = w * omega % mod ) {int x = c[j + k], y = c[j + k + i] * w % mod;c[j + k] = ( x + y ) % mod;c[j + k + i] = ( x - y + mod ) % mod;}}if( op == -1 ) {int inv = qkpow( len, mod - 2 );for( int i = 0;i < len;i ++ ) c[i] = c[i] * inv % mod;} }void init( int n ) {fac[0] = inv[0] = 1;for( int i = 1;i <= n;i ++ ) fac[i] = fac[i - 1] * i % mod;inv[n] = qkpow( fac[n], mod - 2 );for( int i = n - 1;i;i -- ) inv[i] = inv[i + 1] * ( i + 1 ) % mod; }int C( int n, int m ) { return fac[n] * inv[m] % mod * inv[n - m] % mod; }signed main() {int n, m, s;scanf( "%lld %lld %lld", &n, &m, &s );for( int i = 0;i <= m;i ++ ) scanf( "%lld", &W[i] );init( max( n, m ) );int lim = min( m, n / s );for( int i = 0;i <= lim;i ++ ) {f[i] = fac[i] * C(m, i) % mod * fac[n] % mod * qkpow(inv[s], i) % mod * inv[n - i * s] % mod * qkpow(m - i, n - i * s) % mod;g[i] = (i & 1) ? mod - inv[i] : inv[i];}reverse( f, f + lim + 1 );int l;for( len = 1, l = 0;len <= (lim << 1);len <<= 1, l ++ );for( int i = 0;i < len;i ++ ) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1 );NTT( f, 1 ), NTT( g, 1 );for( int i = 0;i < len;i ++ ) f[i] = f[i] * g[i] % mod;NTT( f, -1 );int ans = 0;for( int i = 0;i <= lim;i ++ ) ( ans += W[i] * inv[i] % mod * f[lim - i] ) %= mod;printf( "%lld\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的[HAOI2018] 染色（二项式反演+NTT）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。