「P9248」完美的集合
题目
点这里看题目。
分析
“选
注意到，对于定点
统计根为某顶点的连通块的信息是容易的，此处就有一个
加入“选
（正片开始）
问题的主要矛盾来到了“计算
此时就不得不研究模数的性质了。进行一个质因数分解，发现
扩展 Lucas 算法关键为：对于
假如现在要对于
注意到
要想快速地计算这个式子，我们可以考虑计算出
问题来了：这个多项式可能很长，怎么办？观察到三条性质：
-
-
答案对于
5^{23} 取模，而复合的一次式的常数项一定是5 的倍数。 -
合并子问题时，基本运算为“复合一次式”和“卷积”，其中只有“复合一次式”会产生高次项到低次项的影响。而计算
f(x+c) 的过程中，x^{t} 到x^0 的贡献必然带有c^t 的因子。即便是多次复合，包含参数的因式也是一个次数为t 的齐次式。
以上三条可以导出，次数不低于
特别地，当
具体操作的时候，需要对于每一个
复杂度不算了，能过就是了。
代码
#include <bits/stdc++.h>
#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<typename _T>
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<typename _T>
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;
}