[UOJ 113][UER #2]手机的生产
转载请注明出处：http://danihao123.is-programmer.com/
神哎……
既然与的优先级比或高，那么我们就可以用或把程序切成若干段，每一段的值决定了最后的取值。
考虑从左往右计算某一段。如果有一个手机某一段运算结果为0，那么它会继续往下运算，反之则会停止运算。
对于每一个在前\(i\)段的值都是0，然后开始跑第\(i + 1\)段的手机。他们都会额外产生\(l\)（这一段的fork个数）个手机，并且由于这些手机一被生产出来的返回值就是0，所以新的这些手机在这一段取值为0。而原来的老手机，在这一段的取值事1，于是之后的运算就不会接着做了。
这样一来，我们就可以动态维护在之前的段里的返回值全是0的手机，然后就可以做了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
using ll = long long;
const int maxn = 100005;
const ll ha = 998244353LL;
bool op[maxn];
int main() {
std::vector<int> vec;
int last = 0;
int n; scanf("%d", &n);
for(int i = 1; i <= (n - 1); i ++) {
char buf[5]; scanf("%s", buf);
if(buf[0] == '|') {
vec.push_back(i - last);
last = i;
}
}
vec.push_back(n - last);
ll pre0 = 1LL;
ll ans = 1LL;
for(auto x : vec) {
ans += (pre0 * (ll(x))) % ha; ans %= ha;
pre0 = (pre0 * (ll(x))) % ha;
}
printf("%lld\n", ans);
return 0;
}
评论 (0)
