【Codeforces 696C】PLEASE

相关链接

题目传送门:http://codeforces.com/contest/696/problem/C
官方题解:http://codeforces.com/blog/entry/46031
中文题面:http://www.cnblogs.com/DarkTong/p/5674920.html

解题报告

用全概率公式可以推得\(p(i) = – \frac{{1 – p[i – 1]}}{2}\)
然后推一推通项公式可以得到\(p(i) = \frac{{{{( – 1)}^i} + {2^{i – 1}}}}{{3 \cdot {2^{i – 1}}}}\)
然后我们惊奇的发现\({{{( – 1)}^i} + {2^{i – 1}}}\)总可以被3整除
而\({{{( – 1)}^i} + {2^{i – 1}}}\)又是一个奇数,与2的整次幂肯定不能约分
于是搞一搞快速幂什么的就可以了

Code

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

const int MOD = 1000000007;
const int REV = 333333336;
const int N = 100000+9;

LL k,arr[N];

inline int pow(LL w, LL t) {
	int ret = 1; while (t) {
		if (t & 1) ret = (LL)ret*w % MOD;
		w = w*w % MOD; t >>= 1;
	} return ret;
}

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	k = read(); int tag = 1;
	for (int i=1;i<=k;i++) tag = ((arr[i] = read()) == 1 && tag);
	if (tag) puts("0/1");
	else {
		LL numerator=REV,denominator=2; tag = -1;
		for (int i=1;i<=k;i++) if (arr[i]%2 == 0) tag = 1;
		for (int i=1;i<=k;i++) denominator = pow(denominator,arr[i]);
		(denominator *= pow(2LL,MOD-2LL)) %= MOD;
		(numerator *= denominator + tag) %= MOD;
		printf("%d/%d",(int)numerator,(int)denominator);
	}
	return 0;
}

2 thoughts to “【Codeforces 696C】PLEASE”

  1. Hey would you mind sharing which blog platform you’re using? I’m looking to start my own blog soon but I’m having a hard time choosing between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your design and style seems different then most blogs and I’m looking for something completely unique. P.S My apologies for being off-topic but I had to ask!

Leave a Reply

Your email address will not be published. Required fields are marked *