题目
题意简述
link.
有一个 (n) 个元素的集合，你需要进行 (m) 次操作。每次操作选择集合的一个非空子集，要求该集合不是已选集合的并的子集。求操作的方案数，对 (10^9+7) 取模。
数据规模
(nle3 imes10^4)。
( ext{Solution})
显然当 (n<m)，答案为 (0)，先特判掉。
首先列一个 naive 的 DP 方程，令 (f(i,j)) 为前 (i) 次操作选出的集合并大小为 (j) 的方案数。易有：
[f(i,j)=sum_{k=1}^j2^{j-k}{n-(j-k)choose k}f(i-1,j-k)
]
那么答案为 (sum_{i=1}^nf(m,i))。暴力 DP 是 (mathcal{O}(mn^2)) 的。不过很显然这个式子是一个卷积的形式。把它变一下形：
[f(i,j)=frac{1}{(n-j)!}sum_{k=1}^jfrac{1}{k!}cdot2^{j-k}[n-(j-k)]!f(i-1,j-k)
]
忽略毒瘤的模数，每次转移 NTT 就可以了，复杂度 (mathcal{O}(mnlog n))。
这个 (f) 不太好优化。我们换一种形式，令 (g(i,j)) 为前 (i) 次操作选出前 (j) 个元素的方案数。所以 (g(i,j)=frac{f(i,j)}{nchoose j})。那么对于 (g(1))，有 (g(1,i)=[0<ile n])。来考虑两层状态的合并：
[g(u+v,i)=sum_{j=0}^ig(u,j)g(v,i-j){ichoose j}(2^j)^v
]
理解一下：把 (u+v) 次操作和 (i) 个选出的元素分拆成两步完成：第一步选 (j) 个元素，第二步选 (i-j) 个。由于要在 (i) 里拿出 (j) 个给第一步（或说拿出 (i-j) 给第二步），所以有系数 (ichoose j)。关键点在于 ((2^u)^j)：在第一步中，我们已经选出了 (j) 个元素，所以在第二步的每次操作，都可以任意取 (j) 个元素的子集，故有系数 ((2^j)^v)。
向卷积形式靠拢：
[g(u+v,i)=i!sum_{j=0}^ifrac{2^{jv}g(u,j)}{j!}cdotfrac{g(v,i-j)}{(i-j)!}
]
倍增处理 (g) 即可。复杂度 (mathcal{O}(nlog nlog m))。
代码
这里用 MTT 实现任模 NTT。要特别留意每一步的取模嗷 qwq。
#include <cmath>
#include <cstdio>
#include <iostream>
typedef long long LL;
const int MAXN = 1 << 16, P = 1e9 + 7;
const double PI = acos ( -1 );
int n, m, len, lg, rev[MAXN + 5], fac[MAXN + 5], ifac[MAXN + 5], pwr[MAXN + 5];
int F[MAXN + 5], ans[MAXN + 5];
struct Complex {
double x, y;
Complex () {} Complex ( const double tx, const double ty ): x ( tx ), y ( ty ) {}
inline Complex operator + ( const Complex t ) const { return Complex ( x + t.x, y + t.y ); }
inline Complex operator - ( const Complex t ) const { return Complex ( x - t.x, y - t.y ); }
inline Complex operator * ( const Complex t ) const { return Complex ( x * t.x - y * t.y, x * t.y + y * t.x ); }
inline Complex operator / ( const double t ) const { return Complex ( x / t, y / t ); }
} omega[MAXN + 5];
inline void FFT ( const int n, Complex* A, const int tp ) {
for ( int i = 0; i < n; ++ i ) if ( i < rev[i] ) std::swap ( A[i], A[rev[i]] );
for ( int i = 2, stp = 1; i <= n; i <<= 1, stp <<= 1 ) {
for ( int j = 0; j < n; j += i ) {
for ( int k = 0; k < stp; ++ k ) {
Complex w ( omega[n / stp * k].x, tp * omega[n / stp * k].y );
Complex ev ( A[j + k] ), ov ( w * A[j + k + stp] );
A[j + k] = ev + ov, A[j + k + stp] = ev - ov;
}
}
}
if ( ! ~ tp ) for ( int i = 0; i < n; ++ i ) A[i] = A[i] / n;
}
inline void initFFT ( const int lg ) {
int n = 1 << lg;
for ( int i = 0; i < n; ++ i ) rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) << lg >> 1 );
for ( int i = 1; i < n; i <<= 1 ) {
for ( int k = 0; k < i; ++ k ) {
omega[n / i * k] = Complex ( cos ( PI * k / i ), sin ( PI * k / i ) );
}
}
}
inline void polyConv ( const int n, const int* A, const int* B, int* C ) {
static Complex highA[MAXN + 5], highB[MAXN + 5], lowA[MAXN + 5], lowB[MAXN + 5];
for ( int i = 0; i < n; ++ i ) {
lowA[i].x = A[i] & 0x7fff, highA[i].x = A[i] >> 15;
lowB[i].x = B[i] & 0x7fff, highB[i].x = B[i] >> 15;
lowA[i].y = highA[i].y = lowB[i].y = highB[i].y = 0;
}
FFT ( n, lowA, 1 ), FFT ( n, highA, 1 ), FFT ( n, lowB, 1 ), FFT ( n, highB, 1 );
for ( int i = 0; i < n; ++ i ) {
Complex la ( lowA[i] ), ha ( highA[i] ), lb ( lowB[i] ), hb ( highB[i] );
lowA[i] = ha * hb, highA[i] = la * hb, lowB[i] = ha * lb, highB[i] = la * lb;
}
FFT ( n, lowA, -1 ), FFT ( n, highA, -1 ), FFT ( n, lowB, -1 ), FFT ( n, highB, -1 );
for ( int i = 0; i < n; ++ i ) {
C[i] = ( ( 1ll << 30 ) % P * ( LL ( round ( lowA[i].x ) ) % P ) % P
+ ( LL ( round ( highA[i].x ) ) % P << 15 ) % P
+ ( LL ( round ( lowB[i].x ) ) % P << 15 ) % P
+ ( LL ( round ( highB[i].x ) ) % P ) ) % P;
}
}
inline int qkpow ( int a, int b, const int p = P ) {
int ret = 1;
for ( ; b; a = 1ll * a * a % p, b >>= 1 ) ret = 1ll * ret * ( b & 1 ? a : 1 ) % p;
return ret;
}
inline void init ( const int n ) {
fac[0] = ifac[0] = pwr[0] = 1;
for ( int i = 1; i <= n; ++ i ) {
fac[i] = 1ll * i * fac[i - 1] % P;
pwr[i] = ( pwr[i - 1] << 1 ) % P;
}
ifac[n] = qkpow ( fac[n], P - 2 );
for ( int i = n - 1; i; -- i ) ifac[i] = ( i + 1ll ) * ifac[i + 1] % P;
}
inline void add ( const int fn, const int fm ) {
if ( ! fn ) {
for ( int i = 0; i <= n; ++ i ) ans[i] = F[i];
return ;
}
static int A[MAXN + 5], B[MAXN + 5];
for ( int i = 0; i <= n; ++ i ) {
A[i] = 1ll * ans[i] * ifac[i] % P * qkpow ( 2, 1ll * i * fm % ( P - 1 ) ) % P;
B[i] = 1ll * F[i] * ifac[i] % P;
}
for ( int i = n + 1; i < len; ++ i ) A[i] = B[i] = 0;
polyConv ( len, A, B, ans );
for ( int i = 0; i <= n; ++ i ) ans[i] = 1ll * ans[i] * fac[i] % P;
for ( int i = n + 1; i < len; ++ i ) ans[i] = 0;
}
inline void shift ( const int cur ) {
static int A[MAXN + 5], B[MAXN + 5];
for ( int i = 0; i <= n; ++ i ) {
A[i] = 1ll * F[i] * ifac[i] % P * qkpow ( 2, 1ll * i * cur % ( P - 1 ) ) % P;
B[i] = 1ll * F[i] * ifac[i] % P;
}
for ( int i = n + 1; i < len; ++ i ) A[i] = B[i] = 0;
polyConv ( len, A, B, F );
for ( int i = 0; i <= n; ++ i ) F[i] = 1ll * F[i] * fac[i] % P;
for ( int i = n + 1; i < len; ++ i ) F[i] = 0;
}
int main () {
scanf ( "%d %d", &m, &n );
if ( m > n ) return puts ( "0" ), 0;
len = 1, lg = 0;
for ( ; len <= n << 1; len <<= 1, ++ lg );
initFFT ( lg ), init ( n );
for ( int i = 1; i <= n; ++ i ) F[i] = 1;
for ( int i = 0, cur = 0; 1 << i <= m; ++ i ) {
if ( ( m >> i ) & 1 ) add ( cur, 1 << i ), cur |= 1 << i;
shift ( 1 << i );
}
int sum = 0;
for ( int i = 0; i <= n; ++ i ) {
sum = ( sum + 1ll * ans[i] * fac[n] % P * ifac[i] % P * ifac[n - i] ) % P;
}
printf ( "%d
", sum );
return 0;
}