中文题意

给出 $n$ 个数，你需要操作的次数是 $m=\Pi a_i$ ，现在你有3个盘子，假设编号是0,1,2，初始我们编号1中有一个小球，每次操作可以在0,2中选择一个盘子和1做一次交换，并且重新做编号。问做 $m$ 次操作之后，小球还留在1号盘子的概率是多少，输出最简分数的形式。 $n\le10^5,a_i\le10^{18}$ 。

Solution

我们首先使用动态规划进行递推最终答案，我们假设 $f[i][0/1/2]$ 代表第 $i$ 步留在0,1,2号盘子的概率。那么我们得到转移方程是。 $\\f[i][0]=f[i-1][0]/2+f[i-1][1]/2\\f[i][1]=f[i-1][0]/2+f[i-1][2]/2\\f[i][2]=f[i-1][1]/2+f[i-1][2]/2$
对于每个位置都可能从旁边转移过来以及之前就保留在这个位置，并且这次选择要选择正确的移动。
那么观察我们不难发现0号和2号盘子是对称的。所以我们可以得到 $f[i][0]=f[i][2]$ 把它带入 $f[i][1]$ 中。
再次化简你会得到： $\\f[i][0]=f[i-1][0]/2+f[i-1][1]/2\\f[i][1]=f[i-1][0]$
再把 $f[i-1][1]$ 看成 $f[i-2][0]$ 带入 $f[i][0]$ 中，你会得到: $\\f[i][0]=f[i-1][0]/2+f[i-2][0]/2$
同理再做一次代换可以得到： $\\f[i+1][1]=f[i][0]/2+f[i-1][1]/2\\f[i][1]=f[i-1][1]/2+f[i-2][1]/2$ 。
那么我们就拿到了一个线性递推的求解 $f[i][1]$ 的方程，但是这是一个二阶递推式，还需要做一次化简。
我们把式子写成 $a_n=\frac{1}{2}*a_{n-1}+\frac{1}{2}*a_{n-2}$ 。套用特征方程的求解办法，可以解得每一项的通解。这里给个比较好的学习地址把，如果还有不会求解二阶递推式的同学可以去这里学学传送门
特征方程是 $2r^2-r-1=0$ ，求解到2个根分别是 $x_1=-\frac{1}{2},x_2=1$ 。
再带入 $a_0=1,a_1=0$ ，求解到 $A*x_1^n+B*x_2^n=a_n$ ，解得 $A=\frac{2}{3},B=1$ 。
那么我们就解到一阶的 $a_n$ 通项公式， $a_n=\frac{2}{3}*(-\frac{1}{2})^n+\frac{1}{3}\\a_n=\frac{(-1)^n+2^{n-1}}{3*2^{n-1}}$
当然化简到上面的 $a_n$ 式子你就几乎成功了，再看约分的事情，因为分子一定是一个奇数，所以分子分母之间一定没有因子2，所以2的幂次直接照算即可。但是我们再看3，枚举几项你会发现，当 $n$ 是奇数的时候 $2^{n-1}\%3=1,(-1)^n=-1$ ，他们一累加一定是3的倍数，同理当 $n$ 是偶数的时候 $2^{n-1}\%3=2,(-1)^n=1$ ，他们一累加也变成3的倍数了，所以得出结论，分子分母一定可以把3约掉。
最后再处理幂次的时候，按照费马小定理就模上 $mod-1$ 即可，注意幂次可能取模变成0了，这样如果你直接在后面快速幂求解 $n-1$ 就会出问题，小心这样的小陷阱。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 1e6 + 7;
ll n, m;
ll p[N];
void solve() {
    n = read();
    ll mi = 1;
    rep(i, 1, n) {
        ll x = read();
        mi = x % (MOD - 1) * mi % (MOD - 1);
    }
    if (mi == 0)    mi = MOD - 1;
    ll up = qpow(2, mi - 1, MOD);
    if (mi & 1)    up = (up - 1 + MOD) % MOD;
    else up = (up + 1) % MOD;
    up = up * qpow(3, MOD - 2, MOD) % MOD;
    ll dw = qpow(2, mi - 1, MOD);
    printf("%lld/%lld\n", up, dw);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

【每日一题】2月24日PLEASE 动态规划+特征方程

中文题意

Solution