Decision
题意
从 \([0,t]\) 中等概率的选取两个数字 \(v_1,v_2\), 定义序列 \(X\) 有 \(X_0=v1+v2,X_{n+1}=(aX_n+c) \mod m\)。如果 \(X_{|v1-v2|}\) 是偶数,则获胜,求获胜概率
范围:\(2\le m \le 10^6,0\le a,c \lt m, 0\le t \lt \frac{m}{2}\)
分析
枚举 \(sum = v_1+v_2\) 的值,考虑 \(dis = |v_1-v_2|\) 的可能取值。
先考虑\(sum \le t\) 的情况
- 若 \(sum\) 是偶数,那么\(dis\) 可能取值为 \(0,2,\cdots sum\), 并且0只会被取到一次,其他偶数会取到两次(为什么会取到两次?考虑 \(v_1\)与\(v_2\) 对称取值)。
- 若 \(sum\) 是奇数,那么\(dis\) 可能取值为 \(1,3,\cdots sum\), 所有数字都会取到两次
然后\(sum\gt t\) 的情况类似
- 若 \(sum\) 是偶数,那么\(dis\) 可能取值为 \(0,2,\cdots 2*t-sum\), 并且0只会被取到一次,其他偶数会取到两次。
- 若 \(sum\) 是奇数,那么\(dis\) 可能取值为 \(1,3,\cdots 2*t-sum\), 所有数字都会取到两次
现在的问题是如何快速根据\(sum\), 求出所有值的贡献,注意到 \(X_0=sum\), 同组 \(dis\) 都只会隔2递增,我们可以预处理出每个sum往后跳两次的位置在哪里(跳是指 \(sum' = (a*sum+c)\pmod m\)), 然后倍增处理即可。
const int N = 1000000 + 5;
int T, t, a, c, m;
int nxt[N], tt;
int f[N][21], d[N][21];
ll res;
void get(int x, int p){
for(int i=tt;i>=0;i--){
if(p >= (1 << i)){
res += 2*d[x][i]; // 每个dis的贡献都是二倍
p -= 1 << i;
x = f[x][i];
}
}
}
ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a%b);}
int main(){
scanf("%d", &T);
while(T--){
scanf("%d%d%d%d",&t, &a, &c, &m);
for(int i=0;i<m;i++){
nxt[i] = (1ll * a * i + c) % m; //nxt[i] 表示 i 往后跳一次的位置
}
for(int i=0;i<m;i++){
f[i][0] = nxt[nxt[i]]; // f[i][0] 表示 i 往后跳2^i次的位置
// d 数组计算贡献,当坐标为偶数时贡献为 1,注意这里并没有计算起点 i 的贡献,后面需要单独计算
d[i][0] = f[i][0] % 2 == 0;
}
tt = log2(2*t-1) + 1;
for(int j=1;j<=tt;j++) {
for(int i=0;i<m;i++){
f[i][j] = f[f[i][j-1]][j-1];
d[i][j] = d[i][j-1] + d[f[i][j-1]][j-1];
}
}
res = 0;
// 枚举 sum
for(int i=0;i<=2*t;i++) {
if(i <= t) {
if(i % 2 == 0) {
res ++; // sum 为偶数,dis 为 0 时有一次贡献
get(i, i / 2); // 计算之后的贡献,跳跃次数为 sum / 2
} else {
// sum 为奇数,单独计算 dis 为 1 时的贡献
if(nxt[i] % 2 == 0) res += 2;
// 从 nxt[i] 开始,计算剩下的贡献
get(nxt[i], (i - 1) / 2);
}
} else {
if(i % 2 == 0) {
res ++;
get(i, (2 * t - i)/2);
} else {
if(nxt[i] % 2 == 0) res += 2;
get(nxt[i], (2 * t - i - 1) / 2);
}
}
}
ll all = 1ll*(t + 1) * (t + 1);
ll g = gcd(all, res);
printf("%lld/%lld\n", res/g, all/g);
}
return 0;
}
其他: 场上并没有想出这道题,列出X关于sum和dis的通项之后手足无措,sum和dis奇偶性保持一致,sum确定后,dis是等间隔取到的,但是仍然没有想到可以用倍增处理。