tqyaaaaang's Blog

POJ 2118 ( 特征多项式 )

题目链接:http://poj.org/problem?id=2118

解法

这题其实是矩乘的模板题,这里就不讲了,讲特征多项式优化的方法。

如果不会特征多项式的看这里

然后直接上就行了。

代码

// I/O stream
#include <iostream>
#include <iomanip>

// Algorithms & Maths
#include <cmath>
#include <numeric>
#include <algorithm>

// C headers
#include <cstdlib>
#include <cstdio>

// String
#include <string>
#include <cstring>

// STL
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>

// Exeption
#include <exception>
#include <stdexcept>
#include <cassert>

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)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 207;
const int MOD = 10000;

int n, k;
int a[MAXN], b[MAXN];

struct pT
{
	pT ()
	{
		INIT ( a, 0 );
	}

	pT operator * ( const pT &x ) const
	{
		pT ans;
		lp ( i, 0, n ) lp ( j, 0, n ) ( ans[i+j] += a[i] * x[j] ) %= MOD;
		lpdi ( i, n+n-2, n ){
			lpi ( j, 1, n ) ( ans[i-j] += ans[i] * b[j] ) %= 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];
	}

	int a[MAXN];
};

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

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

	scanf ( "%d", &n );
	if ( !n ) return false;
	lp ( i, 0, n ) scanf ( "%d", &a[i] );
	lpi ( i, 1, n ) scanf ( "%d", &b[i] );
	scanf ( "%d", &k );
	return true;
}

void work ()
{
	// main work

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

	int ans = 0;
	lp ( i, 0, n ) ( ans += ret[i] * a[i] ) %= MOD;

	printf ( "%d\n", ans );
}



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