AGC 034 F RNG and XOR
发布于
# algorithm
题目连接: https://atcoder.jp/contests/agc034/tasks/agc034_f
道理我都懂，可是不看题解不到啊……
1 题意
给定一个数字
对于 中每个数字都有一个
现在有一个数 , 一开始为
每一次操作会随机选择一个数字 （其中 ，选中 的概率为 ）
然后令
问使 的期望次数
2 思路
先令
令 表示从 到 的期望次数，这和从 到 显然是一样的
接着有一个非常显然的式子
然后我们就可以得到这个式子
(f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \oplus (p_0, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\ \= ( x, f_1 - 1, f_2 - 1, \cdots, f_{2^{n-1}} - 1, f_{2^n-1} - 1 )但是 是未知的
注意到 所以左边右边的和是相等的
所以
(f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \oplus (p_0, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\ \= ( f_0 + 2^n - 1, f_1 - 1, f_2 - 1, \cdots, f_{2^{n-1}} - 1, f_{2^n-1} -1 )我们需要的使其中两个式子没有未知数
注意到如果使
那么右边每一个数都会减去
即
于是就可以放进 FWT 里直接做
然后你就发现这东西跑出来是错的……
为什么呢
令
因为 和 FWT 后第一位都是
没有办法倒推出来
但是可以发现 的值是可以平移的
即
那么我们又知道
所以将 每一位都减去 即可
3 Code
#include <cstdio>
const int N = 1 << 20;
const int mod = 998244353;
int n;
int a[N], b[N], p[N], sum;
inline i
nt add( int a, int b ) { return ( a + b ) % mod; }
inline int mul( int a, int b ) { return ( 1LL * a * b ) % mod; }
inline void add_eq( int &a, int b ) { a = ( a + b ) % mod; }
inline void mul_eq( int &a, int b ) { a = ( 1LL * a * b ) % mod; }
int ksm( int a, int p ) {
int res = 1;
while( p ) {
if( p & 1 )
res = mul( res, a );
a = mul( a, a );
p >>= 1;
}
return res;
}
inline int inv( int a ) { return ksm( a, mod - 2 ); }
void XOR( int *f, int len, int x = 1 ) {
for( int o = 2, k = 1; o <= len; o <<= 1, k <<= 1 ) {
for( int i = 0; i < len; i += o ) {
for( int j = 0; j < k; j ++ ) {
add_eq( f[ i + j ], f[ i + j + k ] );
f[ i + j + k ] = add( f[ i + j ], add( - f[ i + j + k ], - f[ i + j + k ] ) );
mul_eq( f[ i + j ], x ); mul_eq( f[ i + j + k ], x );
}
}
}
}
int main() {
#ifdef woshiluo
freopen( "F.in", "r", stdin );
freopen( "F.out", "w", stdout );
#endif
scanf( "%d", &n );
n = 1 << n;
for( int i = 0; i < n; i ++ ) {
scanf( "%d", &a[i] );
sum += a[i];
b[i] = mod - 1;
}
sum = inv(sum);
for( int i = 0; i < n; i ++ ) {
p[i] = mul( a[i], sum );
}
b[0] = n - 1; p[0] -= 1;
XOR( b, n ); XOR( p, n );
for( int i = 0; i < n; i ++ ){
mul_eq( b[i], inv( p[i] ) );
}
XOR( b, n, inv(2) );
for( int i = 0; i < n; i ++ ) {
printf( "%d\n", ( ( add( b[i], -b[0] ) + mod ) % mod ) );
}
}