fps/inversion-formula.hpp
Depends on
Code
#pragma once
#include "formal-power-series.hpp"
template < typename mint >
FormalPowerSeries < mint > n2_inv ( const FormalPowerSeries < mint >& f ) {
assert ( f . empty () == false && f [ 0 ] != mint ( 0 ));
int n = f . size ();
mint if0 = f [ 0 ]. inverse ();
FormalPowerSeries < mint > g ( n );
g [ 0 ] = if0 ;
for ( int k = 1 ; k < n ; k ++ ) {
for ( int i = 0 ; i < k ; i ++ ) g [ k ] += g [ i ] * f [ k - i ];
g [ k ] *= - if0 ;
}
return g ;
}
template < typename mint >
FormalPowerSeries < mint > n2_log ( const FormalPowerSeries < mint >& f ) {
assert ( f . empty () == false && f [ 0 ] == 1 );
int n = f . size (), mod = mint :: get_mod ();
static vector < mint > invs { mint ( 1 ), mint ( 1 )};
while (( int ) invs . size () <= n ) {
int i = invs . size ();
invs . push_back (( - invs [ mod % i ]) * ( mod / i ));
}
FormalPowerSeries < mint > g ( n );
for ( int k = 0 ; k < n - 1 ; k ++ ) {
for ( int i = 0 ; i < k ; i ++ ) g [ k + 1 ] -= g [ i + 1 ] * f [ k - i ] * ( i + 1 );
g [ k + 1 ] *= invs [ k + 1 ];
g [ k + 1 ] += f [ k + 1 ];
}
return g ;
}
template < typename mint >
FormalPowerSeries < mint > n2_exp ( const FormalPowerSeries < mint >& f ) {
assert ( f . empty () == false && f [ 0 ] == 0 );
int n = f . size (), mod = mint :: get_mod ();
static vector < mint > invs { mint ( 1 ), mint ( 1 )};
while (( int ) invs . size () <= n ) {
int i = invs . size ();
invs . push_back (( - invs [ mod % i ]) * ( mod / i ));
}
FormalPowerSeries < mint > g ( n );
g [ 0 ] = 1 ;
for ( int k = 0 ; k < n - 1 ; k ++ ) {
for ( int i = 0 ; i <= k ; i ++ ) g [ k + 1 ] += f [ i + 1 ] * g [ k - i ] * ( i + 1 );
g [ k + 1 ] *= invs [ k + 1 ];
}
return g ;
}
template < typename mint >
FormalPowerSeries < mint > n2_sqrt ( const FormalPowerSeries < mint >& f ) {
assert ( f . empty () == false && f [ 0 ] == 1 );
int n = f . size ();
static mint inv2 = mint ( 2 ). inverse ();
FormalPowerSeries < mint > g ( n );
g [ 0 ] = 1 ;
for ( int k = 1 ; k < n ; k ++ ) {
g [ k ] = f [ k ];
for ( int i = 1 ; i <= k - 1 ; i ++ ) g [ k ] -= g [ i ] * g [ k - i ];
g [ k ] *= inv2 ;
}
return g ;
}
#line 2 "fps/inversion-formula.hpp"
#line 2 "fps/formal-power-series.hpp"
template < typename mint >
struct FormalPowerSeries : vector < mint > {
using vector < mint >:: vector ;
using FPS = FormalPowerSeries ;
FPS & operator += ( const FPS & r ) {
if ( r . size () > this -> size ()) this -> resize ( r . size ());
for ( int i = 0 ; i < ( int ) r . size (); i ++ ) ( * this )[ i ] += r [ i ];
return * this ;
}
FPS & operator += ( const mint & r ) {
if ( this -> empty ()) this -> resize ( 1 );
( * this )[ 0 ] += r ;
return * this ;
}
FPS & operator -= ( const FPS & r ) {
if ( r . size () > this -> size ()) this -> resize ( r . size ());
for ( int i = 0 ; i < ( int ) r . size (); i ++ ) ( * this )[ i ] -= r [ i ];
return * this ;
}
FPS & operator -= ( const mint & r ) {
if ( this -> empty ()) this -> resize ( 1 );
( * this )[ 0 ] -= r ;
return * this ;
}
FPS & operator *= ( const mint & v ) {
for ( int k = 0 ; k < ( int ) this -> size (); k ++ ) ( * this )[ k ] *= v ;
return * this ;
}
FPS & operator /= ( const FPS & r ) {
if ( this -> size () < r . size ()) {
this -> clear ();
return * this ;
}
int n = this -> size () - r . size () + 1 ;
if (( int ) r . size () <= 64 ) {
FPS f ( * this ), g ( r );
g . shrink ();
mint coeff = g . back (). inverse ();
for ( auto & x : g ) x *= coeff ;
int deg = ( int ) f . size () - ( int ) g . size () + 1 ;
int gs = g . size ();
FPS quo ( deg );
for ( int i = deg - 1 ; i >= 0 ; i -- ) {
quo [ i ] = f [ i + gs - 1 ];
for ( int j = 0 ; j < gs ; j ++ ) f [ i + j ] -= quo [ i ] * g [ j ];
}
* this = quo * coeff ;
this -> resize ( n , mint ( 0 ));
return * this ;
}
return * this = (( * this ). rev (). pre ( n ) * r . rev (). inv ( n )). pre ( n ). rev ();
}
FPS & operator %= ( const FPS & r ) {
* this -= * this / r * r ;
shrink ();
return * this ;
}
FPS operator + ( const FPS & r ) const { return FPS ( * this ) += r ; }
FPS operator + ( const mint & v ) const { return FPS ( * this ) += v ; }
FPS operator - ( const FPS & r ) const { return FPS ( * this ) -= r ; }
FPS operator - ( const mint & v ) const { return FPS ( * this ) -= v ; }
FPS operator * ( const FPS & r ) const { return FPS ( * this ) *= r ; }
FPS operator * ( const mint & v ) const { return FPS ( * this ) *= v ; }
FPS operator / ( const FPS & r ) const { return FPS ( * this ) /= r ; }
FPS operator % ( const FPS & r ) const { return FPS ( * this ) %= r ; }
FPS operator - () const {
FPS ret ( this -> size ());
for ( int i = 0 ; i < ( int ) this -> size (); i ++ ) ret [ i ] = - ( * this )[ i ];
return ret ;
}
void shrink () {
while ( this -> size () && this -> back () == mint ( 0 )) this -> pop_back ();
}
FPS rev () const {
FPS ret ( * this );
reverse ( begin ( ret ), end ( ret ));
return ret ;
}
FPS dot ( FPS r ) const {
FPS ret ( min ( this -> size (), r . size ()));
for ( int i = 0 ; i < ( int ) ret . size (); i ++ ) ret [ i ] = ( * this )[ i ] * r [ i ];
return ret ;
}
// 前 sz 項を取ってくる。sz に足りない項は 0 埋めする
FPS pre ( int sz ) const {
FPS ret ( begin ( * this ), begin ( * this ) + min (( int ) this -> size (), sz ));
if (( int ) ret . size () < sz ) ret . resize ( sz );
return ret ;
}
FPS operator >> ( int sz ) const {
if (( int ) this -> size () <= sz ) return {};
FPS ret ( * this );
ret . erase ( ret . begin (), ret . begin () + sz );
return ret ;
}
FPS operator << ( int sz ) const {
FPS ret ( * this );
ret . insert ( ret . begin (), sz , mint ( 0 ));
return ret ;
}
FPS diff () const {
const int n = ( int ) this -> size ();
FPS ret ( max ( 0 , n - 1 ));
mint one ( 1 ), coeff ( 1 );
for ( int i = 1 ; i < n ; i ++ ) {
ret [ i - 1 ] = ( * this )[ i ] * coeff ;
coeff += one ;
}
return ret ;
}
FPS integral () const {
const int n = ( int ) this -> size ();
FPS ret ( n + 1 );
ret [ 0 ] = mint ( 0 );
if ( n > 0 ) ret [ 1 ] = mint ( 1 );
auto mod = mint :: get_mod ();
for ( int i = 2 ; i <= n ; i ++ ) ret [ i ] = ( - ret [ mod % i ]) * ( mod / i );
for ( int i = 0 ; i < n ; i ++ ) ret [ i + 1 ] *= ( * this )[ i ];
return ret ;
}
mint eval ( mint x ) const {
mint r = 0 , w = 1 ;
for ( auto & v : * this ) r += w * v , w *= x ;
return r ;
}
FPS log ( int deg = - 1 ) const {
assert ( ! ( * this ). empty () && ( * this )[ 0 ] == mint ( 1 ));
if ( deg == - 1 ) deg = ( int ) this -> size ();
return ( this -> diff () * this -> inv ( deg )). pre ( deg - 1 ). integral ();
}
FPS pow ( int64_t k , int deg = - 1 ) const {
const int n = ( int ) this -> size ();
if ( deg == - 1 ) deg = n ;
if ( k == 0 ) {
FPS ret ( deg );
if ( deg ) ret [ 0 ] = 1 ;
return ret ;
}
for ( int i = 0 ; i < n ; i ++ ) {
if (( * this )[ i ] != mint ( 0 )) {
mint rev = mint ( 1 ) / ( * this )[ i ];
FPS ret = ((( * this * rev ) >> i ). log ( deg ) * k ). exp ( deg );
ret *= ( * this )[ i ]. pow ( k );
ret = ( ret << ( i * k )). pre ( deg );
if (( int ) ret . size () < deg ) ret . resize ( deg , mint ( 0 ));
return ret ;
}
if ( __int128_t ( i + 1 ) * k >= deg ) return FPS ( deg , mint ( 0 ));
}
return FPS ( deg , mint ( 0 ));
}
static void * ntt_ptr ;
static void set_fft ();
FPS & operator *= ( const FPS & r );
void ntt ();
void intt ();
void ntt_doubling ();
static int ntt_pr ();
FPS inv ( int deg = - 1 ) const ;
FPS exp ( int deg = - 1 ) const ;
};
template < typename mint >
void * FormalPowerSeries < mint >:: ntt_ptr = nullptr ;
/**
* @brief 多項式/形式的冪級数ライブラリ
* @docs docs/fps/formal-power-series.md
*/
#line 4 "fps/inversion-formula.hpp"
template < typename mint >
FormalPowerSeries < mint > n2_inv ( const FormalPowerSeries < mint >& f ) {
assert ( f . empty () == false && f [ 0 ] != mint ( 0 ));
int n = f . size ();
mint if0 = f [ 0 ]. inverse ();
FormalPowerSeries < mint > g ( n );
g [ 0 ] = if0 ;
for ( int k = 1 ; k < n ; k ++ ) {
for ( int i = 0 ; i < k ; i ++ ) g [ k ] += g [ i ] * f [ k - i ];
g [ k ] *= - if0 ;
}
return g ;
}
template < typename mint >
FormalPowerSeries < mint > n2_log ( const FormalPowerSeries < mint >& f ) {
assert ( f . empty () == false && f [ 0 ] == 1 );
int n = f . size (), mod = mint :: get_mod ();
static vector < mint > invs { mint ( 1 ), mint ( 1 )};
while (( int ) invs . size () <= n ) {
int i = invs . size ();
invs . push_back (( - invs [ mod % i ]) * ( mod / i ));
}
FormalPowerSeries < mint > g ( n );
for ( int k = 0 ; k < n - 1 ; k ++ ) {
for ( int i = 0 ; i < k ; i ++ ) g [ k + 1 ] -= g [ i + 1 ] * f [ k - i ] * ( i + 1 );
g [ k + 1 ] *= invs [ k + 1 ];
g [ k + 1 ] += f [ k + 1 ];
}
return g ;
}
template < typename mint >
FormalPowerSeries < mint > n2_exp ( const FormalPowerSeries < mint >& f ) {
assert ( f . empty () == false && f [ 0 ] == 0 );
int n = f . size (), mod = mint :: get_mod ();
static vector < mint > invs { mint ( 1 ), mint ( 1 )};
while (( int ) invs . size () <= n ) {
int i = invs . size ();
invs . push_back (( - invs [ mod % i ]) * ( mod / i ));
}
FormalPowerSeries < mint > g ( n );
g [ 0 ] = 1 ;
for ( int k = 0 ; k < n - 1 ; k ++ ) {
for ( int i = 0 ; i <= k ; i ++ ) g [ k + 1 ] += f [ i + 1 ] * g [ k - i ] * ( i + 1 );
g [ k + 1 ] *= invs [ k + 1 ];
}
return g ;
}
template < typename mint >
FormalPowerSeries < mint > n2_sqrt ( const FormalPowerSeries < mint >& f ) {
assert ( f . empty () == false && f [ 0 ] == 1 );
int n = f . size ();
static mint inv2 = mint ( 2 ). inverse ();
FormalPowerSeries < mint > g ( n );
g [ 0 ] = 1 ;
for ( int k = 1 ; k < n ; k ++ ) {
g [ k ] = f [ k ];
for ( int i = 1 ; i <= k - 1 ; i ++ ) g [ k ] -= g [ i ] * g [ k - i ];
g [ k ] *= inv2 ;
}
return g ;
}
Back to top page