题目
点这里看题目。
分析
很不错的题目。看起来怎么一点都不签到？
首先需要深入地观察，(x|y) 和 (x&y) 到底代表着什么？这实际上取决于我们观察它们的角度：
- 站在运算的角度，我们的逻辑是：输入 (x,y)，我们最终得到 (x|y) 或者 (x&y)；
- 而由于 (x|y,x& yin{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)}
ight)f_{n-1}
]
这样我们就可以得到一个 (O(n)) 的算法。
小结：
-
这里将“二元运算”看作“某种选择”相当有意思。当然，这种看法实际上并不取决于参与运算的元素个数；
需要注意的是，将“运算”看作“选择”能够简化问题的条件还有一个，就是选出某个元素的概率易于计算，否则问题仍然会显得困难。
-
为了方便处理，我们将方案数转化为了概率。需要注意的是，平时我们可能会将概率转化为方案数，这个过程当然也是可逆的，视时而用。
代码
#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( '
' );
return 0;
}