CF696C(计数推公式+欧拉降幂)

题意: 一个推式子的题目.题目给你三个杯子,以及一个币,开始的时候币在中间杯子,每次你都可以控制两侧杯子和中间杯子交换,问你n次之后在中间杯子的概率.其中

思路:注意到,交换了n轮后会产生种局面,而且,当前的产生的局面在下一轮一定不会产生.于是我们假设为交换i轮之后产生的局面数,为答案,显然有:,.于是,.(这里求首项的时候别把公比乘进去了)

,注意到,,所以我们让3作为逆元,此时就避免了取gcd.由于n过大,所以我们使用欧拉降幂.即当a,n互质时,.当n为素数时,.最后注意一点,当b mod φ(n)为0时,要加上φ(n).

代码:

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
// #define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 1e5 + 10, MOD = 1e9 + 7;
int k, n, x, mu;
int qmi(int a, int k, int p) {
	int res = 1;
	while (k) {
		if (k & 1) res = res * a % p;
		k >>= 1;
		a = a * a % p;
	}
	return res;
}
void solve() {
	qio >> k;
	mu = MOD - 1;
	int n = 1;
	for (int i = 1; i <= k; ++i) qio >> x, n = n * (x % mu) % mu;
	if (n == 0) n += mu;
	if (n & 1) qio << (qmi(2, n - 1, MOD) - 1) * (qmi(3, MOD - 2, MOD)) % MOD << "/" << qmi(2, n - 1, MOD) << "\n";
	else qio << (qmi(2, n - 1, MOD) + 1) * (qmi(3, MOD - 2, MOD)) % MOD << "/" << qmi(2, n - 1, MOD) << "\n";
}
signed main()  {
	// IOS;
	int T = 1;
	// qio >> T;
	while (T--) solve();
}