传送门：【HDU】5197 DZY Loves Orzing
题目分析：
首先申明，我不会 dp 方程= =……这个东西给队友找出来了，然后我就是套这个方程做题的Qrz……
对于这题，因为 n2 个数互不相同，所以每一列都可以单独考虑。设 dpni 表示长度为 n 的排列，能恰好看见i个人的方案数，根据队友的发现， dpni 就等于 |sni| ，其中 sni 是第一类 Stirling 数。（不要问我为什么是这个，我不知道……）
由于对于第一类 Stirling 数我们有：
Sn=x(x−1)(x−2)⋯(x−n+1)
=∑ni=1(x+1−i)
用多项式表示则为：
Sn=∑ni=1sinxi
则我们的 dp 方程可以表示为：
dpn=∑ni=1|sin|xi
由 sin=(−1)n+i|sin| 得：
dpn=∑ni=1(−1)n+isinxi
因此我们只要求的 Stirling 数就可以得到我们对应的dp值。
然而我们怎么去求 Stirling 数呢？看到多个多项式相乘，很容易我们可以想到用 FFT 去优化，但是如果是简单的从左往右做 n−1 次 FFT 的话，显然复杂度爆表。
那我们该怎么办呢？
这时候一个自然的想法是对 FFT 之间的乘法分治！因为我们用高阶多项式和低阶多项式相乘，会导致很多时间上的浪费，这时候我们就可以考虑用类似于启发式合并的思想去进行多项式乘法：每次取出阶数最小的两个多项式进行 FFT ，这样我们复杂度就保证了。（这个过程可以用优先队列实现）
最后的答案即：
ans=(n2)!(n!)2∏ni=1dpain
其中 ai 为输入数据。这里还有个问题，就是 (n2)! 太大了怎么办？这个好说，打个表呗（对于给定的模数P，注意到 n2≥P 时 ans=0 ）
时间复杂度即：
n2⋅2log2+n4⋅4log4+⋯+2⋅n2logn2+nlogn
=∑logni=1nlogi
=O(nlog2n)
然后由于题目给的模数P=999948289恰为费马素数，因此我们可以将 FFT 换成 NTT 来保证答案精度。（算法中我用的原根为 g=13 ）
时间复杂度： O(nlog2n)
空间复杂度： O(→_→ 看脸 )
my code:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#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 mod = ;
const int MAXN = ;
const int g = ;
struct Node {
int idx , n ;
Node () {}
Node ( int idx , int n ) : idx ( idx ) , n ( n ) {}
bool operator < ( const Node& a ) const {
if ( n != a.n ) return n > a.n ;
return idx > a.idx ;
}
} ;
vector < int > G[MAXN] ;
int x1[MAXN << ] , x2[MAXN << ] ;
int A[MAXN] ;
int f[MAXN] ;
int invf[MAXN] ;
int ff[MAXN] = { , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , } ;
int m , root ;
int power ( int a , int b ) {
LL res = , tmp = a ;
while ( b ) {
if ( b & ) res = res * tmp % mod ;
tmp = tmp * tmp % mod ;
b >>= ;
}
return ( int ) res ;
}
void NTT ( int y[] , int n , int rev ) {
for ( int i = , j , k , t ; i < n ; ++ i ) {
for ( j = , k = n >> , t = i ; k ; k >>= , t >>= ) j = j << | t & ;
if ( i < j ) swap ( y[i] , y[j] ) ;
}
for ( int s = , ds = ; s <= n ; ds = s , s <<= ) {
int wn = power ( g , ( mod - ) / s ) ;
if ( rev < ) wn = power ( wn , mod - ) ;
for ( int k = , w = ; k < ds ; ++ k , w = ( LL ) w * wn % mod ) {
for ( int i = k , t ; i < n ; i += s ) {
y[i + ds] = ( y[i] - ( t = ( LL ) w * y[i + ds] % mod ) + mod ) % mod ;
y[i] = ( y[i] + t ) % mod ;
}
}
}
if ( rev < ) {
int inv = power ( n , mod - ) ;
for ( int i = ; i < n ; ++ i ) y[i] = ( LL ) y[i] * inv % mod ;
}
}
void solve () {
priority_queue < Node > q ;
for ( int i = ; i <= m ; ++ i ) {
scanf ( "%d" , &A[i] ) ;
G[i].clear () ;
}
if ( ( LL ) m * m >= mod ) {
printf ( "0\n" ) ;
return ;
}
for ( int i = ; i <= m ; ++ i ) {
G[i].push_back ( ( - i + mod ) % mod ) ;
G[i].push_back ( ) ;
q.push ( Node ( i , ) ) ;
}
while ( !q.empty () ) {
int x = q.top ().idx ;
q.pop () ;
if ( q.empty () ) {
root = x ;
break ;
}
int y = q.top ().idx ;
q.pop () ;
int n1 = G[x].size () , n2 = G[y].size () , nn = n1 + n2 - ;
int n = ;
while ( n < nn ) n <<= ;
for ( int i = ; i < n ; ++ i ) x1[i] = i < n1 ? G[x][i] : ;
for ( int i = ; i < n ; ++ i ) x2[i] = i < n2 ? G[y][i] : ;
NTT ( x1 , n , ) ;
NTT ( x2 , n , ) ;
for ( int i = ; i < n ; ++ i ) x1[i] = ( LL ) x1[i] * x2[i] % mod ;
NTT ( x1 , n , - ) ;
G[x].clear () ;
for ( int i = ; i < nn ; ++ i ) G[x].push_back ( x1[i] ) ;
q.push ( Node ( x , nn ) ) ;
}
int ans = power ( invf[m] , m ) ;
int mm = m * m , x ;
for ( x = ; x + <= mm ; x += ) ans = ( LL ) ans * ff[x / ] % mod ;
for ( ++ x ; x <= mm ; ++ x ) ans = ( LL ) ans * x % mod ;
for ( int i = ; i <= m ; ++ i ) {
if ( ( m + A[i] ) % == ) ans = ( LL ) ans * G[root][A[i]] % mod ;
else ans = ( LL ) ans * ( mod - G[root][A[i]] ) % mod ;
}
printf ( "%d\n" , ans ) ;
}
int main () {
f[] = ;
for ( int i = ; i < MAXN ; ++ i ) {
f[i] = ( LL ) i * f[i - ] % mod ;
invf[i] = power ( f[i] , mod - ) ;
}
while ( ~scanf ( "%d" , &m ) ) solve () ;
return ;
}
![js与jquery常用方法总结[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)