tqyaaaaang's Blog

HDU 4914 ( 特征多项式+FFT )

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4914

题意

给定n, a, b, p, q,定义\(f(k)\)如下:
$$
f(k)=
\begin{cases}
1 & k <= 0 \\
a * f(k-p) + b * f(k-q) & k > 0
\end{cases}
$$
求\(f(n)\)。

解法

模板题。用特征多项式优化一下矩阵乘法,然后用FFT优化多项式乘法就行了。

不会特征多项式的看这里

代码

#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define PQ priority_queue
#define GT(type) greater < type >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

#define CX complex < double >

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 170007;
const double PI = acos ( -1.0 );
const int MOD = 119;

int n, A, B, p, q, k;

namespace fft
{
	int nm, tn;
	CX ca[MAXN], cb[MAXN], cans[MAXN], omega[MAXN];

	void init ()
	{
		nm = ( n - 1 ) << 1;
		tn = 1;
		while ( tn <= nm ) tn <<= 1;
		lp ( i, 0, tn ) omega[i] = CX ( cos ( 2 * PI * i / tn ), sin ( 2 * PI * i / tn ) );
	}

	void fft ( CX ar[] )
	{
		for ( int i = 0, j = 0; i < tn; ++i ){
			if ( i > j ) swap ( ar[i], ar[j] );
			for ( int bt = tn >> 1; bt && !( ( j ^= bt ) & bt ); bt >>= 1 );
		}

		int m;
		CX x, y;
		for ( int i = 2; i <= tn; i <<= 1 ){
			m = i >> 1;
			for ( int j = 0; j < tn; j += i ){
				lp ( k, 0, m ){
					x = ar[j+k], y = ar[j+k+m] * omega[tn/i*k];
					ar[j+k] = x + y;
					ar[j+k+m] = x - y;
				}
			}
		}
	}

	void mul ( const int a[], const int b[], int ans[] )
	{
		lp ( i, 0, n ) ca[i] = a[i], cb[i] = b[i];
		lp ( i, n, tn ) ca[i] = cb[i] = 0;
		fft ( ca );
		fft ( cb );
		lp ( i, 0, tn ) cans[i] = ca[i] * cb[i], omega[i] = conj ( omega[i] );
		fft ( cans );
		lpi ( i, 0, nm ) ans[i] = SC ( int, floor ( cans[i].real () / tn + 0.5 ) ) % MOD;
		lp ( i, 0, tn ) omega[i] = conj ( omega[i] );
	}
}

class pT
{
public:
	pT ()
	{
		INIT ( a, 0 );
	}

	pT operator * ( const pT &x ) const
	{
		pT ans;
		fft::mul ( a, x.a, ans.a );
		lpdi ( i, n+n-2, n ) ( ans[i-p] += A * ans[i] ) %= MOD, ( ans[i-q] += B * ans[i] ) %= MOD, ans[i] = 0;
		return ans;
	}

	void operator *= ( const pT &x )
	{
		( *this ) = ( *this ) * x;
	}

	int operator [] ( int i ) const
	{
		return a[i];
	}

	int & operator [] ( int i )
	{
		return a[i];
	}

private:
	int a[MAXN];
};

int f[MAXN];

void init ();
bool input ();
void work ();

int getval ( int i );
pT qpow ( pT &a, int b );



int main()
{
	init();
	while ( input() )
		work();
}



void init ()
{
	// Init Everything Here

	ios::sync_with_stdio ( false );
}

bool input ()
{
	// input method

	return ( scanf ( "%d%d%d%d%d", &k, &A, &B, &p, &q ) == 5 );
}

void work ()
{
	// main work

	A %= MOD, B %= MOD;
	n = q;
	fft::init ();

	pT base;
	base[1] = 1;
	pT ret = qpow ( base, k );

	int ans = 0;
	f[0] = 1;
	lp ( i, 1, n ) f[i] = ( A * getval ( i - p ) + B * getval ( i - q ) ) % MOD;
	lp ( i, 0, n ) ( ans += ret[i] * f[i] ) %= MOD;
	printf ( "%d\n", ans );
}



int getval ( int i )
{
	if ( i <= 0 ) return 1;
	else return f[i];
}

pT qpow ( pT &a, int b )
{
	pT base = a, ans;
	ans[0] = 1;
	while ( b ){
		if ( b & 1 ) ans *= base;
		base *= base;
		b >>= 1;
	}
	return ans;
}

Tianqi Yang

View Comments
Navigation