相关链接
题目传送门: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; }
As soon as I detected this website I went on reddit to share some of the love with them.
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!