\(\mathcal{Description}\)

用 \(m\) 种颜色为长为 \(n\) 的序列染色，每个位置一种颜色。对于一种染色方案，其价值为 \(w(\text{出现恰 }s\text{ 次的颜色种数})\)（\(w(0..m)\) 给定），求所有染色方案的价值和。

\(n\le10^7\)，\(m\le10^5\)，答案对 \(p=1004535809=479\times2^{21}+1\) 取模。

\(\mathcal{Solution}\)

记 \(l=\min\{m,\lfloor\frac{n}{s}\rfloor\}\)，显然只能对于 \(i=0..l\)，分别算出 \(w(i)\) 的贡献次数。考虑容斥，令 \(f(i)\) 表示至少 \(i\) 种颜色恰好出现 \(s\) 次的染色方案数。那么：

\[f(i)=\binom{m}i\frac{n!}{(s!)^i(n-is)!}(m-i)^{n-is}
\]

即：选出 \(i\) 种颜色钦定恰好出现 \(s\) 次；多重集排列安排已被染色的 \(is\) 个位置和剩下的 \((n-is)\) 个位置；为 \((n-is)\) 个位置任选未使用的颜色。

此后，令 \(g(i)\) 表示恰好 \(i\) 种颜色恰好出现 \(s\) 次的染色方案数，容斥：

\[\begin{aligned}
g(i)&=\sum_{j=i}^l(-1)^{l-i}\binom{j}if_j\\
&=\sum_{j=i}^l(-1)^{l-j}\frac{j!}{i!(j-i)!}f_j\\
&=\frac{1}{i!}\sum_{j=i}^l\frac{(-1)^{l-j}}{(j-i)!}(j!f_j)
\end{aligned}
\]

很俗套 trick，翻转乘积式任意一项就能写成卷积形式，NTT 求出 \(g(i)\) 即可。

复杂度 \(\mathcal O(n+l\log l)\)。

\(\mathcal{Code}\)

/* Clearink */

#include <cstdio>

#define rep( i, l, r ) for ( int i = l, rpbound##i = r; i <= rpbound##i; ++i )

#define per( i, r, l ) for ( int i = r, rpbound##i = l; i >= rpbound##i; --i )

const int MAXN = 1e7, MAXM = 1e5, MOD = 1004535809, G = 3, MAXLEN = 1 << 18;

int n, m, s, w[MAXM + 5], f[MAXLEN + 5], g[MAXLEN + 5], rev[MAXLEN + 5];

int fac[MAXN + 5], ifac[MAXN + 5]; // warning: 77MB.

inline char fgc () {

	static char buf[1 << 17], *p = buf, *q = buf;

	return p == q && ( q = buf + fread ( p = buf, 1, 1 << 17, stdin ), p == q )

		? EOF : *p++;

}

inline int rint () {

	int x = 0; char s = fgc ();

	for ( ; s < '0' || '9' < s; s = fgc () );

	for ( ; '0' <= s && s <= '9'; s = fgc () ) x = x * 10 + ( s ^ '0' );

	return x;

}

inline void iswp ( int& a, int& b ) { a ^= b ^= a ^= b; }

inline int imin ( const int a, const int b ) { return a < b ? a : b; }

inline int imax ( const int a, const int b ) { return a < b ? b : a; }

inline int mul ( const long long a, const int b ) { return a * b % MOD; }

inline int sub ( int a, const int b ) { return ( a -= b ) < 0 ? a + MOD : a; }

inline int add ( int a, const int b ) { return ( a += b ) < MOD ? a : a - MOD; }

inline int mpow ( int a, int b ) {

	int ret = 1;

	for ( ; b; a = mul ( a, a ), b >>= 1 ) ret = mul ( ret, b & 1 ? a : 1 );

	return ret;

}

inline int inv ( const int n ) { return mpow ( n, MOD - 2 ); }

inline void init ( const int n ) {

	fac[0] = 1;

	rep ( i, 1, n ) fac[i] = mul ( i, fac[i - 1] );

	ifac[n] = inv ( fac[n] );

	per ( i, n - 1, 0 ) ifac[i] = mul ( i + 1, ifac[i + 1] );

}

inline int comb ( const int n, const int m ) {

	return n < m ? 0 : mul ( fac[n], mul ( ifac[m], ifac[n - m] ) );

}

inline void NTT ( const int n, int* A, const int flg ) {

	rep ( i, 0, n - 1 ) if ( i < rev[i] ) iswp ( A[i], A[rev[i]] );

	for ( int i = 2, stp = 1; i <= n; i <<= 1, stp <<= 1 ) {

		int w = mpow ( G, ( MOD - 1 ) / i );

		if ( !~flg ) w = inv ( w );

		for ( int j = 0; j < n; j += i ) {

			for ( int k = j, wk = 1; k < j + stp; ++k, wk = mul ( wk, w ) ) {

				int ev = A[k], ov = mul ( wk, A[k + stp] );

				A[k] = add ( ev, ov ), A[k + stp] = sub ( ev, ov );

			}

		}

	}

	if ( !~flg ) {

		int in = inv ( n );

		rep ( i, 0, n - 1 ) A[i] = mul ( in, A[i] );

	}

}

int main () {

	n = rint (), m = rint (), s = rint ();

	init ( imax ( n, m ) );

	rep ( i, 0, m ) w[i] = rint ();

	int mx = imin ( m, n / s );

	for ( int i = 0, fp = 1; i <= mx; ++i, fp = mul ( fp, fac[s] ) ) {

		f[i] = mul ( fac[i], mul ( mul ( comb ( m, i ), mpow ( m - i, n - i * s ) ),

			mul ( fac[n], inv ( mul ( fp, fac[n - i * s] ) ) ) ) );

	}

	rep ( i, 0, mx ) {

		g[i] = ( ( mx - i ) & 1 ? sub : add )( 0, inv ( fac[mx - i] ) );

	}

	int len = 1, lgv = 0;

	for ( ; len < mx + 1 << 1; len <<= 1, ++lgv );

	rep ( i, 0, len - 1 ) rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) << lgv >> 1 );

	NTT ( len, f, 1 ), NTT ( len, g, 1 );

	rep ( i, 0, len - 1 ) f[i] = mul ( f[i], g[i] );

	NTT ( len, f, -1 );

	int ans = 0;

	rep ( i, 0, mx ) {

		ans = add ( ans, mul ( w[i], mul ( f[i + mx], ifac[i] ) ) );

	}

	printf ( "%d\n", ans );

	return 0;

}

巴特西

Solution -「HAOI 2018」「洛谷 P4491」染色

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章