欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  网络运营

HDU6847 Decision 基环外向树+倍增

程序员文章站 2022-06-15 22:12:50
题意随机生成两个数v1v1v1,v2v2v2∈[0,t]\in[0,t]∈[0,t]X0=v1+v2X_{0} = v1 + v2X0​=v1+v2Xn+1=(aXn+c)mod  mX_{n+1} = (aX_n+c) \mod mXn+1​=(aXn​+c)modm求X∣v1−v2∣X_{|v1-v2|}X∣v1−v2∣​是偶数的概率m>t/2,m≤106m>t/2,m\leq 10^6m>t/2,m≤106分析每个数变成一个点,就是一个基环外向树,设XyX_{y}Xy​...

题意

随机生成两个数v1v1,v2v2[0,t]\in[0,t]
X0=v1+v2X_{0} = v1 + v2
Xn+1=(aXn+c)mod  mX_{n+1} = (aX_n+c) \mod m
Xv1v2X_{|v1-v2|}是偶数的概率
m>t/2m106m>t/2,m\leq 10^6

分析

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

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

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

贡献最后除以(t+1)2(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

相关标签: 倍增 hdu