[UVa] 10338 - Mischievous Children

題目網址:  https://goo.gl/juVUy4

題意:
(from luckycat)


解法:
跟 http://mobcs.blogspot.tw/2015/06/uva-10329-combinatorial-expression.html 一樣，但是更簡單。

TAG: Math, Prime,

注意:

程式碼:

	/**
	* Tittle: 10338 - Mischievous Children
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/30
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 30
	typedef vector<int> VI;
	typedef long long ll;
	// declarations
	int n;
	char buf[N];
	int cnt[N];
	int ansFact[N];
	int fact[N][N];
	VI prime;
	ll ans;
	// functions
	void init( void )
	{
	prime.push_back(2);
	prime.push_back(3);
	prime.push_back(5);
	prime.push_back(7);
	prime.push_back(11);
	prime.push_back(13);
	prime.push_back(17);
	prime.push_back(19);
	int tmp;
	clr( fact, 0 );
	FOR( i, 2, 20 ) {
	tmp = i;
	for( int v:prime ) {
	if( v*v > tmp ) break;
	while( tmp%v == 0 ) {
	tmp /= v;
	++fact[i][v];
	}
	}
	if( tmp != 1 )
	fact[i][tmp] = 1;
	}
	}
	void factorize( int v )
	{
	if( v > 0 ) {
	for( int k:prime )
	ansFact[k] += fact[v][k];
	} else if( v < 0 ) {
	v = -v;
	for( int k:prime )
	ansFact[k] -= fact[v][k];
	}
	}
	ll fastpow( ll base, int e )
	{
	ll ret = 1LL;
	while( e ) {
	if( e&1 )
	ret *= base;
	base = base*base;
	e >>= 1;
	}
	return ret;
	}
	void solve( void )
	{
	ans = 1LL;
	clr( ansFact, 0 );
	clr( cnt, 0 );
	int sl = strlen( buf );
	FOR( i, 0, sl-1 )
	++cnt[buf[i]-'A'];
	FOR( i, 2, sl )
	factorize(i);
	FOR( i, 0, 25 ) if( cnt[i]>1 ) {
	FOR( j, 2, cnt[i] )
	factorize(-j);
	}
	for( int v:prime )
	ans *= fastpow( v, ansFact[v] );
	}
	// main function
	int main( void )
	{
	// input
	scanf( "%d", &n );
	init();
	FOR( ti, 1, n ) {
	scanf( "%s", buf );
	solve();
	printf( "Data set %d: %lld\n", ti, ans );
	}
	return 0;
	}

view raw 10338 - Mischievous Children.cpp hosted with ❤ by GitHub