VolBIT Formulas Blitz : G-L

少し難しいのもあるけどがんばろう。
http://codeforces.com/contest/630/problem/G
http://codeforces.com/contest/630/problem/H
http://codeforces.com/contest/630/problem/I
http://codeforces.com/contest/630/problem/J
http://codeforces.com/contest/630/problem/K
http://codeforces.com/contest/630/problem/L

G. Challenge Pennants

を答えよう。

ll combi(ll N_, ll C_) {
	ll ret=1;
	int i;
	FOR(i,C_) ret*=N_-i, ret/=(i+1);
	return ret;
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:combi(P_+Q_-1,Q_);};


void solve() {
	ll N;
	cin>>N;
	
	cout<<hcomb(N,3)*hcomb(N,5)<<endl;
	
}

H. Benches

を答えよう。

void solve() {
	int N,i;
	
	cin>>N;
	ll ret=1;
	FOR(i,5) ret*=N-i;
	FOR(i,5) ret/=(i+1);
	
	ret=ret*ret*120;
	cout<<ret<<endl;
}

I. Parking Lot

N文字同じ場所が続くのは1箇所しかない。

N文字の両隣は残り3種の文字で、それ以外は何でも良い。
N文字の部分が両端にある場合、隣に来る文字は1つである点に注意して数え上げよう。

void solve() {
	ll N,ret=0;
	
	cin>>N;
	//left,right
	ret=2*3*(1LL<<(2*(2*N-2-N-1)));
	//other
	ret+=(N-3)*3*3*(1LL<<(2*(2*N-2-N-2)));
	cout<<4*ret<<endl;
}

J. Divisibility

2～10のLCMは2520なので、N/2520を答えればよい。

void solve() {
	ll N;
	ll r=1;
	
	cin>>N;
	for(ll i=2;i<=10;i++) r=r*i/__gcd(i,r);
	cout<<N/r<<endl;
}

K. Indivisibility

0～2519のうち、何個2520と互いに素な整数があるか数えよう。
その数をdとすると、N/2520*d個と、あとはNを2520で割った余りの分だけ答えに加算する。

void solve() {
	int yes[2540]={};
	int i,x;
	int sum=0;
	for(i=0;i<2520;i++) {
		yes[i]=1;
		for(x=2;x<=10;x++) if(i%x==0) yes[i]=0;
		sum+=yes[i];
	}
	
	ll N;
	cin>>N;
	ll ret = N/2520*sum;
	N%=2520;
	FOR(i,N+1) ret+=yes[i];
	cout<<ret<<endl;
}

I. Parking Lot

オーバーフローしないように、問題文どおり計算するだけ。
答えの出力にLeading zeroを含めるよう注意。

void solve() {
	ll N;
	cin>>N;
	N=N/10000*10000+(N/1000%10)+(N/100%10*1000)+(N/10%10*10)+(N%10*100);
	ll ret=N*N%100000*N%100000*N%100000*N%100000;
	_P("%05d\n",(int)ret);
}

まとめ

ここらへんはまだ難しくない。