Codeforces 696C PLEASE(수론)

제목:
컵 세 개를 드릴게요. 처음에 중간에 있는 컵에 열쇠가 있어요. 매번 중간에 있는 컵과 좌우 양쪽에 있는 컵을 교환하고 매번 선택할 때마다 확률을 기다리는 거예요. n번 조작한 후에 열쇠가 중간에 있는 컵의 확률이 얼마냐고 물어보고 점수로 표시해 주세요.
해법:
이 문제는 두 가지 처리해야 할 것이 있는데 하나는 n이 매우 크기 때문에 n의 각 인자를 주는 것이다. 그러나 이것은 어렵지 않다. 가격 행렬의 빠른 멱은 계산할 수 있다. 그리고 dp의 방정식은 매우 잘 추측된다. 바로 dp[i]=(1-dp[i-1])*0.5이다.그리고 그는 또 가장 간단한 분수 형식으로 이것을 반드시 이 dp방정식을 간소화해야 한다고 표시했다. 우리는 고등학교의 지식을 활용하고 통항 공식을 맞추면 된다. 이것은 내가 말하지 않겠다. 할 수 없는 것은 반고등학교 수학책에 가라.마지막으로 얻은 결과는 dp[i]=(1-(-1/2)^(n-1)/(3*2^(n-1))이다. 필요한 점수 형식이고mod1e9+7이 필요하기 때문에 우리는 상하 두 개의 상호질을 해야만 요구에 부합할 수 있다. 우리는 이 분자를 (2^(n-1)+(-1)^n/3로 바꾸고 분모는 1/2^(n-1)로 만들어야 한다. 이 두 가지가 바로 상호질이라는 것을 증명하기 위해서는 몇 가지 규칙을 찾아볼 수 있다.직접 상하분은 요구에 부합되지 않는데 왜 직접 나누면 안 되는지 간단하게 설명할 수 있습니다. 만약에 n-1이 짝수라면 2^(n-1)% 3=1, 1을 빼면 0입니다. 그러면 서로 질적일 수 없습니다. n-1은 홀수 같은 이치입니다.

//  Created by  CQU_CST_WuErli
//  Copyright (c) 2016 CQU_CST_WuErli. All rights reserved.
//
//#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define CLR(x) memset(x,0,sizeof(x))
#define OFF(x) memset(x,-1,sizeof(x))
#define MEM(x,a) memset((x),(a),sizeof(x))
#define BUG cout << "I am here" << endl
#define lookln(x) cout << #x << "=" << x << endl
#define SI(a) scanf("%d", &a)
#define SII(a,b) scanf("%d%d", &a, &b)
#define SIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
const int INF_INT=0x3f3f3f3f;
const long long INF_LL=0x7f7f7f7f;
const int MOD=1e9+7;
const double eps=1e-10;
const double pi=acos(-1);
typedef long long  ll;
using namespace std;

int n;
ll a[100010];

ll ksm(ll a, ll x) {
    if (x == 0LL) return 1LL % MOD;
    ll ret = ksm(a, x / 2);
    ret = ret * ret % MOD;
    if (x & 1) ret = ret * a % MOD;
    return ret;
}

int main(int argc, char const *argv[]) {
#ifdef LOCAL
    freopen("C:\\Users\\john\\Desktop\\in.txt","r",stdin);
    // freopen("C:\\Users\\john\\Desktop\\out.txt","w",stdout);
#endif
    while (SI(n) == 1) {
        for (int i = 1; i <= n; i++)
            scanf("%I64d", a + i);
        ll p, q = 2LL;
        int flag = 0;
        for (int i = 1; i <= n; i++) {
            q = ksm(q, a[i]);
            if (!(a[i] & 1)) flag = 1;
        }
        q = q * ksm(2, MOD - 2) % MOD;
        p = (q + MOD + (flag ? 1 : -1)) % MOD;
        p = p * ksm(3, MOD - 2) % MOD;
        cout << p << '/' << q << endl;
    }
    return 0;
}