题解
理解题面
也就是要给这n-1个运算符安排顺序,统计ans为true的方案数 t ,统计ans为false的方案数 f ,
求 t / ( t+f ) (mod 998244535 )
思路
考虑最后算那种运算符,那么就有n-1种选择
(1)最后算 & :ans为true:左项和右项同时为true
ans为false:左true右false,左false右true,左false右false
(2)最后算 | :ans为true:左项和右项同时为true,左true右false,左false右true
ans为false:左false右false
(3)最后算 ^:ans为true:左右不同,左true右false,左false右true
ans为false:左右相同,左true右true,左false右false
应用乘法分步原理和加法原理统计
SOLVE
注意
最后面除法转换成乘法逆元了
代码
#include<bits/stdc++.h> using namespace std; const int mod=998244353; int n; long long ans; char s[505],opr[505]; //s存操作状态(t或f),opr存操作符(&,|,^) long long t[505][505],f[505][505]; //t存值为true的方案数,f存值为false的方案数 inline int read1() { int ans=0; char last=' ',ch=getchar(); while(ch<'0'||ch>'9') last=ch,ch=getchar(); while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar(); if(last=='-') ans=-ans; return ans; } inline char read2() { char c; do { c=getchar(); }while(c==' '||c==' '||c=='