傳送門:【Tinsen】A1493. 城市規劃
前言:
今天很不在狀态= =,NTT裡面竟然同一個地方寫錯兩次……而且腦補的時候明顯比平時遲鈍了很多……
題目分析:
首先我們可以輕易知道N個點能構成的無向圖的個數: 2C2n ,令其等于 d(N) 。然後假設我們固定一個點,枚舉這個點所在連通塊的大小,這樣我們得到N個點的無向連通圖公式:
dp[n]=d(n)−∑n−2i=0Cin−1dp(i+1)⋅d(n−i−1)
=d(n)−∑n−2i=0(n−1)!i!(n−i−1)!d(i+1)⋅d(n−i−1)
=d(n)−∑n−2i=0(n−1)!dp(i+1)i!⋅d(n−i−1)(n−i−1)!
可以發現右邊是一個卷積公式,然後我們可以用 FFT 去優化。同時我們需要使用 CDQ 分治,先遞歸處理cdq(l,m)的部分,然後将(l,m)的貢獻傳遞給(m+1,r),然後我們遞歸計算cdq(m+1,r),由于出題人好心的給了費馬素數,那麼我們就使用 NTT 來保證精度。
PS:出題人資料打錯了……N=4時ans=38。
my code:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std ;
typedef long long LL ;
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
const int MAXN = ;
const int mod = ;
const int g = ;
int n ;
int d[MAXN] ;
int dp[MAXN] ;
int f[MAXN] ;
int invf[MAXN] ;
int x1[MAXN] , x2[MAXN] ;
LL power ( LL a , LL b ) {
LL res = , tmp = a ;
while ( b ) {
if ( b & ) res = res * tmp % mod ;
tmp = tmp * tmp % mod ;
b >>= ;
}
return res ;
}
void NTT ( int y[] , int n , int rev ) {
for ( int i = , j , k , t ; i < n ; ++ i ) {
for ( j = , t = i , k = n >> ; k ; t >>= , k >>= ) {
j = j << | t & ;
}
if ( i < j ) swap ( y[i] , y[j] ) ;
}
for ( int s = , ds = ; s <= n ; ds = s , s <<= ) {
LL wn = power ( g , ( mod - ) / s ) ;
if ( rev < ) wn = power ( wn , mod - ) ;
for ( int k = ; k < n ; k += s ) {
LL w = , t ;
for ( int i = k ; i < k + ds ; ++ i , w = w * wn % mod ) {
y[i + ds] = ( y[i] - ( t = w * y[i + ds] % mod ) + mod ) % mod ;
y[i] = ( y[i] + t ) % mod ;
}
}
}
if ( rev < ) {
LL invn = power ( n , mod - ) ;
for ( int i = ; i < n ; ++ i ) {
y[i] = y[i] * invn % mod ;
}
}
}
void cdq ( int l , int r ) {
if ( l == r ) return ;
int m = ( l + r ) >> ;
cdq ( l , m ) ;
int n1 = ;
while ( n1 <= r - l ) n1 <<= ;
for ( int i = ; i < n1 ; ++ i ) {
x1[i] = i + l <= m ? ( LL ) dp[i + l] * invf[i + l - ] % mod : ;
x2[i] = i + l <= r ? ( LL ) invf[i + ] * d[i + ] % mod : ;
}
NTT ( x1 , n1 , ) ;
NTT ( x2 , n1 , ) ;
for ( int i = ; i < n1 ; ++ i ) {
x1[i] = ( LL ) x1[i] * x2[i] % mod ;
}
NTT ( x1 , n1 , - ) ;
for ( int i = m + ; i <= r ; ++ i ) {
dp[i] = ( dp[i] - ( LL ) f[i - ] * x1[i - l - ] % mod + mod ) % mod ;
}
cdq ( m + , r ) ;
}
void preprocess () {
invf[] = f[] = ;
for ( int i = ; i <= ; ++ i ) {
d[i] = power ( , ( LL ) i * ( i - ) / ) ;
dp[i] = d[i] ;
f[i] = ( LL ) f[i - ] * i % mod ;
invf[i] = power ( f[i] , mod - ) ;
}
d[] = ;
cdq ( , ) ;
}
int main () {
preprocess () ;
while ( ~scanf ( "%d" , &n ) ) printf ( "%d\n" , dp[n] ) ;
return ;
}