「Gym102978B」Bit Operation

题目

点这里看题目。

分析

很不错的题目。看起来怎么一点都不签到?

首先需要深入地观察,\(x|y\) 和 \(x\&y\) 到底代表着什么?这实际上取决于我们观察它们的角度:

  • 站在运算的角度,我们的逻辑是:输入 \(x,y\),我们最终得到 \(x|y\) 或者 \(x\&y\);
  • 而由于 \(x|y,x\& y\in\{x,y\}\),因此我们也可以将 \(x|y,x\& y\) 看作两种选择方式。这样我们就将“运算”结果和 \(x,y\) 本身深度联系在了一起。通过合理地构造 \(|,\&\) 的意义,对于任意的 \((x,y)\),我们都可以使得在两种选法下 \(x,y\) 各被选出恰好一次。

这样问题就变成了,对于原序列中的每一个 1,在多少种方案中它会被选出?

此时对于某一个元素,它被选出取决于最终它在左右均被选出。由于方案本身涉及到操作顺序的问题,我们可以将方案数转化为概率,这样左右的概率就是独立的,且仅与元素个数有关。

因此我们可以设计一个 DP:设 \(f_n\) 表示在 \(n\) 个元素中第一个元素被选出的概率,不难得到:

\[f_n=\left(\frac{n-2}{n-1}+\frac{1}{2(n-1)}\right)f_{n-1} \]

这样我们就可以得到一个 \(O(n)\) 的算法。

小结:

  1. 这里将“二元运算”看作“某种选择”相当有意思。当然,这种看法实际上并不取决于参与运算的元素个数;

    需要注意的是,将“运算”看作“选择”能够简化问题的条件还有一个,就是选出某个元素的概率易于计算,否则问题仍然会显得困难。

  2. 为了方便处理,我们将方案数转化为了概率。需要注意的是,平时我们可能会将概率转化为方案数,这个过程当然也是可逆的,视时而用。

代码

#include <cstdio>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int mod = 998244353;
const int MAXN = 1e6 + 5;

template<typename _T>
void read( _T &x )/*{{{*/
{
	x = 0; char s = getchar(); int f = 1;
	while( ! ( '0' <= s && s <= '9' ) ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
	while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
	x *= f;
}/*}}}*/

template<typename _T>
void write( _T x )/*{{{*/
{
	if( x < 0 ) putchar( '-' ), x = -x;
	if( 9 < x ) write( x / 10 );
	putchar( x % 10 + '0' );
}/*}}}*/

int dp[MAXN];
int inv[MAXN], fac[MAXN];

int A[MAXN];
int N;

inline int Mul( int x, int v ) { return 1ll * x * v % mod; }
inline int Sub( int x, int v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, int v ) { return ( x += v ) >= mod ? x - mod : x; }

void Init( const int n )/*{{{*/
{
	fac[0] = 1; rep( i, 1, n ) fac[i] = Mul( fac[i - 1], i );
	inv[1] = 1; rep( i, 2, n ) inv[i] = Mul( inv[mod % i], mod - mod / i );
}/*}}}*/

int main()
{
	read( N ), Init( N );
	rep( i, 1, N ) read( A[i] );
	dp[1] = 1;
	rep( i, 2, N ) 
		dp[i] = Mul( dp[i - 1], Add( Mul( i - 2, inv[i - 1] ), Mul( inv[2], inv[i - 1] ) ) );
	int ans = 0;
	rep( i, 1, N ) if( A[i] )
		ans = Add( ans, Mul( dp[i], dp[N - i + 1] ) );
	rep( i, 1, N - 1 ) ans = Mul( ans, Mul( 2, i ) );
	write( ans ), putchar( '\n' );
	return 0;
}
上一篇:HDLbits——Rotate100


下一篇:C6678高性能处理平台学习资料第5篇:基于TMS320C6678+XC7K325T的6U CPCIe高性能处理平台