「P9248」完美的集合
crashed
·
2023-05-19 22:34:35
·
题解
题目
点这里看题目。
分析
“选 K 个”的要求是依托答辩，先不管它，考虑 K=1 的情况。
注意到，对于定点 y，满足 \operatorname{dist}(x,y)\times v_y>\mathrm{Max} 的 x 构成树上的一个连通块。于是，对于任意一个集合 S，可以放置测试装置的点也构成树上的一个连通块。因此，做一个“点-边容斥”即可将问题转化为“使得点 x（或边 (x,y) 的两个端点）可以放置测试装置的完美的集合有多少个？”。
统计根为某顶点的连通块的信息是容易的，此处就有一个 O(nm) 的算法。于是，先用一个 O(n^2m)（或 O(nm\log n)）的算法计算出完美的集合的结点价值之和，再花 O(n^2m) 的时间做上述容斥，复杂度即为 O(n^2m)。
加入“选 K 个”的要求后，我们发现对于一个集簇 \mathcal F，可以放置测试装置的点还是形成一个树上的连通块，于是“点-边容斥”还是可行的。只不过，如果“使得点 x（或边 (x,y) 的两个端点）可以放置测试装置的完美的集合”的个数为 t，原先贡献为 \pm t，现在贡献为 \pm\binom{t}{K}，这一点和「十二省联考 2019」希望一模一样。
（正片开始）
问题的主要矛盾来到了“计算 \binom{t}{K}”，其中 t,K 都是（相对于通常情况而言）非常大的数。不过，因为 t\le 2^n，所以上下指标都还能存得下真实值。
此时就不得不研究模数的性质了。进行一个质因数分解，发现 M=11920928955078125=5^{23}，非常的 smooth。所以，我们考虑使用扩展 Lucas 算法。
扩展 Lucas 算法关键为：对于 n，求出 \prod_{1\le k\le n,5\nmid k}k。在模数较小时，我们可以直接利用乘积式的周期性预处理，但现在不行。考虑常规策略——分治计算。特别地，因为结果和模 5 的余数有关，我们考虑从它开始进行分治。
假如现在要对于 n>1，求出 g(n)=\prod_{1\le k\le n,5\nmid k}k。设 m=\lceil\log_5 n\rceil-1 为满足 5^m \prod_{t=0}^{r-1}\left(\prod_{t\times 5^m< k\le (t+1)\times 5^m,5\nmid k}k\right)\cdot \prod_{r\times 5^m< k\le n,5\nmid k}k 注意到 r\times 5^m+k 对于 5 的整除性和 k 相同，所以有： \prod_{r\times 5^m< k\le n,5\nmid k}k=\prod_{0< k\le n-r\times 5^m,5\nmid k}(k+r\times 5^m) 要想快速地计算这个式子，我们可以考虑计算出 f_{n}(x)=\prod_{0 f_n(x)=\prod_{t=0}^{r-1}f_{5^m}(x+t\times 5^m)\cdot f_{n-r\times 5^m}(x+r\times 5^m) 问题来了：这个多项式可能很长，怎么办？观察到三条性质： 答案对于 5^{23} 取模，而复合的一次式的常数项一定是 5 的倍数。 合并子问题时，基本运算为“复合一次式”和“卷积”，其中只有“复合一次式”会产生高次项到低次项的影响。而计算 f(x+c) 的过程中，x^{t} 到 x^0 的贡献必然带有 c^t 的因子。即便是多次复合，包含参数的因式也是一个次数为 t 的齐次式。 以上三条可以导出，次数不低于 23 的项都可以被舍弃，因为它们不会再对常数项造成影响。这样多项式就变得很轻巧了，可以快速地完成运算。 特别地，当 m=0 时，5^m 不再是 5 的倍数。不过，这个边界情况下，直接暴力算一下多项式的乘积即可。 具体操作的时候，需要对于每一个 m 都预处理出 f_{5^m}(x)，最好还可以预处理一个 \prod_{t=0}^{r-1}f_{5^m}(x+t\times 5^m) 的前缀积。 复杂度不算了，能过就是了。 代码 #include #define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ ) #define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- ) typedef long long LL; typedef __int128 ExLL; const LL mod = 11920928955078125; const int MAXLOG = 30, MAXN = 65, MAXM = 10005; template inline void Read( _T &x ) { x = 0; char s = getchar(); bool f = false; while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); } while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); } if( f ) x = -x; } template inline void Write( _T x ) { if( x < 0 ) putchar( '-' ), x = -x; if( 9 < x ) Write( x / 10 ); putchar( x % 10 + '0' ); } inline LL Sub( LL x, const LL &v ) { return ( x -= v ) < 0 ? x + mod : x; } inline LL Add( LL x, const LL &v ) { return ( x += v ) >= mod ? x - mod : x; } inline LL& SubEq( LL &x, const LL &v ) { return ( x -= v ) < 0 ? ( x += mod ) : x; } inline LL& AddEq( LL &x, const LL &v ) { return ( x += v ) >= mod ? ( x -= mod ) : x; } namespace PureCalculation { struct Poly { LL coe[23]; Poly(): coe{} {} }; Poly bas[MAXLOG], pref[MAXLOG][6]; LL sml[23][23], pw[23], pw5[MAXLOG]; LL vpK, factK; int K; inline LL Inv( LL base, LL indx = 9536743164062500 - 1 ) { LL ret = 1; while( indx ) { if( indx & 1 ) ret = ( ExLL ) ret * base % mod; base = ( ExLL ) base * base % mod, indx >>= 1; } return ret; } inline Poly operator * ( const Poly &a, const Poly &b ) { Poly ret; ExLL tmp; rep( i, 0, 22 ) { tmp = 0; rep( j, 0, i ) tmp += ( ExLL ) a.coe[j] * b.coe[i - j]; ret.coe[i] = tmp % mod; } return ret; } inline Poly Shift( const Poly &f, const LL &c ) { if( ! c ) return f; Poly ret; ExLL tmp; pw[0] = 1; rep( i, 1, 22 ) pw[i] = ( ExLL ) pw[i - 1] * c % mod; rep( i, 0, 22 ) { tmp = 0; rep( j, i, 22 ) tmp += ( ExLL ) f.coe[j] * pw[j - i] * sml[j][i]; ret.coe[i] = tmp % mod; } return ret; } inline Poly PartialFactorial( const int &lvl, const LL &n ) { if( lvl == 0 ) return pref[0][n]; int idx = ( n - 1 ) / pw5[lvl]; if( ! idx ) return PartialFactorial( lvl - 1, n ); return Shift( PartialFactorial( lvl - 1, n - idx * pw5[lvl] ), idx * pw5[lvl] ) * pref[lvl][idx]; } inline LL Factorial( const LL &n ) { if( n == 0 ) return 1; return ( ExLL ) PartialFactorial( 25, n ).coe[0] * Factorial( n / 5 ) % mod; } inline LL Legendre( LL n ) { LL ret = 0; for( ; n ; ret += n /= 5 ); return ret; } inline LL Binom( const LL &n ) { if( n < K ) return 0; LL idx = Legendre( n ) - vpK - Legendre( n - K ); if( idx >= 23 ) return 0; LL a = Factorial( n ), c = Factorial( n - K ); return ( ExLL ) a * Inv( c ) % mod * factK % mod * pw5[idx] % mod; } inline void Init( const int &k ) { K = k, pw5[0] = 1; rep( i, 1, 25 ) pw5[i] = pw5[i - 1] * 5; rep( i, 0, 22 ) { sml[i][0] = 1; rep( j, 1, i ) sml[i][j] = Add( sml[i - 1][j], sml[i - 1][j - 1] ); } bas[0].coe[0] = bas[0].coe[1] = 1; pref[0][0].coe[0] = 1; rep( i, 1, 4 ) { Poly tmp; tmp.coe[0] = i, tmp.coe[1] = 1; pref[0][i] = pref[0][i - 1] * tmp; } pref[0][5] = pref[0][4]; rep( i, 1, 25 ) { bas[i] = pref[i - 1][5]; pref[i][0].coe[0] = 1; rep( j, 1, 5 ) pref[i][j] = pref[i][j - 1] * Shift( bas[i], pw5[i] * ( j - 1 ) ); } vpK = Legendre( K ); factK = Inv( Factorial( K ) ); } } namespace OnTree { struct Edge { int to, nxt, w; } Graph[MAXN << 1]; struct Values { LL val, cnt; Values(): val( -1 ), cnt( 0 ) {} Values( LL V ): val( V ), cnt( 1 ) {} Values( LL V, LL C ): val( V ), cnt( C ) {} inline void operator += ( const Values &q ) { if( q.val > val ) val = q.val, cnt = 0; if( q.val == val ) cnt += q.cnt; } inline Values operator + ( const Values &q ) const { if( val > q.val ) return *this; if( val < q.val ) return q; return Values( val, cnt + q.cnt ); } inline Values operator * ( const Values &q ) const { return Values( val + q.val, cnt * q.cnt ); } }; Values dp[MAXN][MAXM]; LL dist[MAXN][MAXN]; int seq[MAXN], siz[MAXN], tot = 0; int edgFr[MAXN], edgTo[MAXN]; int head[MAXN], cnt = 1; int wei[MAXN], val[MAXN]; int N, M, K; LL lim; inline void AddEdge( const int &from, const int &to, const int &W ) { Graph[++ cnt].to = to, Graph[cnt].nxt = head[from]; Graph[cnt].w = W, head[from] = cnt; } inline void Input() { Read( N ), Read( M ), Read( K ), Read( lim ); rep( i, 1, N ) Read( wei[i] ); rep( i, 1, N ) Read( val[i] ); rep( i, 1, N - 1 ) { int u, v, w; Read( u ), Read( v ), Read( w ); AddEdge( u, v, w ), AddEdge( v, u, w ); edgFr[i] = u, edgTo[i] = v; } } void ProcessDist( const int &u, const int &fa, LL *d ) { for( int i = head[u], v ; i ; i = Graph[i].nxt ) if( ( v = Graph[i].to ) ^ fa ) d[v] = d[u] + Graph[i].w, ProcessDist( v, u, d ); } void DFS( const int &u, const int &fa ) { seq[++ tot] = u, siz[u] = 1; for( int i = head[u], v ; i ; i = Graph[i].nxt ) if( ( v = Graph[i].to ) ^ fa ) DFS( v, u ), siz[u] += siz[v]; } inline void ClearDP() { rep( i, 1, N + 1 ) rep( j, 0, M ) dp[i][j] = Values(); } inline void Solve() { Input(); rep( i, 1, N ) ProcessDist( i, 0, dist[i] ); PureCalculation :: Init( K ); Values glb; rep( i, 1, N ) { tot = 0, DFS( i, 0 ); ClearDP(), dp[1][0] = Values( 0 ); rep( j, 1, N ) { int u = seq[j]; rep( k, 0, M ) if( dp[j][k].val >= 0 ) dp[j + siz[u]][k] += dp[j][k]; if( wei[u] <= M ) { Values delt( val[u] ); rep( k, 0, M - wei[u] ) if( dp[j][k].val >= 0 ) dp[j + 1][k + wei[u]] += dp[j][k] * delt; } } rep( k, 0, M ) glb += dp[N + 1][k]; } LL ans = 0; rep( i, 1, N ) { if( wei[i] > M ) continue; tot = 0, DFS( i, 0 ); ClearDP(), dp[1][0] = Values( 0 ); rep( j, 1, N ) { int u = seq[j]; if( u != i ) { rep( k, 0, M ) if( dp[j][k].val >= 0 ) dp[j + siz[u]][k] += dp[j][k]; } if( wei[u] <= M && ( ExLL ) dist[i][u] * val[u] <= lim ) { Values delt( val[u] ); rep( k, 0, M - wei[u] ) if( dp[j][k].val >= 0 ) dp[j + 1][k + wei[u]] += dp[j][k] * delt; } } LL num = 0; rep( k, 0, M ) if( glb.val == dp[N + 1][k].val ) num += dp[N + 1][k].cnt; AddEq( ans, PureCalculation :: Binom( num ) ); } rep( i, 1, N - 1 ) { int x = edgFr[i], y = edgTo[i]; if( wei[x] + wei[y] > M ) continue; tot = 0, DFS( x, 0 ); ClearDP(), dp[1][0] = Values( 0 ); rep( j, 1, N ) { int u = seq[j]; if( u != x && u != y ) { rep( k, 0, M ) if( dp[j][k].val >= 0 ) dp[j + siz[u]][k] += dp[j][k]; } if( wei[u] <= M && ( ExLL ) dist[x][u] * val[u] <= lim && ( ExLL ) dist[y][u] * val[u] <= lim ) { Values delt( val[u] ); rep( k, 0, M - wei[u] ) if( dp[j][k].val >= 0 ) dp[j + 1][k + wei[u]] += dp[j][k] * delt; } } LL num = 0; rep( k, 0, M ) if( glb.val == dp[N + 1][k].val ) num += dp[N + 1][k].cnt; SubEq( ans, PureCalculation :: Binom( num ) ); } Write( ans ), putchar( '\n' ); } } int main() { OnTree :: Solve(); return 0; }
