HDU6847 Decision 基环外向树+倍增

题意

随机生成两个数$v1$,$v2$$\in[0,t]$
$X_{0} = v1 + v2$
$X_{n+1} = (aX_n+c) \mod m$
求$X_{|v1-v2|}$是偶数的概率
$m>t/2，m\leq 10^6$

分析

每个数变成一个点，就是一个基环外向树，设$X_{y}$表示X这个数跳y次的贡献（如果是偶数就是1，奇数就是0）
那么总贡献就是

假设$v1+v2$奇数时
$Ans =2\sum\limits_{x\in\{1,3,5...(v1+v2)\}}{(v1+v2)_x}$

$v1+v2$偶数时
$Ans =2\sum\limits_{x\in\{0,2,4...(v1+v2)\}}{(v1+v2)_x}$

贡献最后除以$(t+1)^2$就好了

代码

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define MP make_pair
#define fi first
#define se second
#define PB push_back
#define CL clear
#define pii pair<int,int>
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = (int)(1e6) + 10;
const int mod = 1e9+7;
const int inf = 1e9;
inline int rd() {
  int p=0; int f=1; char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}
  return p*f;
}
int gcd(int x,int y){return (y==0) ? x : gcd(y,x%y);}
int t,a,c,m; int nxt[N][21],cnt[N][21];
signed main() {
  // freopen("a.in","r",stdin);
  // freopen("a.out","w",stdout);
  int T = rd();
  while(T--) {
    t=rd();a=rd();c=rd();m=rd();
    rep(i,0,m-1) nxt[i][0] = (a*i+c)%m,cnt[i][1] = (nxt[i][0]&1);
    rep(j,1,20) rep(i,0,m-1) {
      nxt[i][j] = nxt[nxt[i][j-1]][j-1];
      if(j>1) cnt[i][j] = cnt[i][j-1] + cnt[nxt[i][j-1]][j-1];
    }
    int fz = 0; int fm = (t+1)*(t+1);
    rep(i,1,t) {
      int lim=i+1,x=i; if(!(i&1)) lim--,x=nxt[x][0];
      dep(j,20,0) if((lim>>j)&1) fz+=cnt[x][j],x=nxt[x][j];
      // printf("%lld : %lld\n",i,fz);
    }
    rep(i,t+1,2*t-1) {
      int lim=2*t-i+1,x=i; if(!(i&1)) lim--,x=nxt[x][0];
      dep(j,20,0) if((lim>>j)&1) fz+=cnt[x][j],x=nxt[x][j];
      // printf("%lld : %lld\n",i,fz);
    }
    fz*=2; fz = fm - fz; int d = gcd(fz,fm);
    printf("%lld/%lld\n",fz/d,fm/d);
  }
  return 0;
}

本文地址：https://blog.csdn.net/weixin_39708759/article/details/107944005