Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


【UER#2】手机的生产

传送门

题目链接

由于电信技术的发展,人人都可以通过手机互相联系。

有一位电信大佬最近想生产一大批手机,然而从生产线上一台一台地生产实在太慢了,于是他想出了一个办法 —— 让手机自我复制。

于是他给手机加上了一个内置的函数 fork()。手机的程序如果调用这个函数,那么手机会生产出一台完全一模一样的手机(包括程序运行状态),并且自己这台的函数返回值为 11,新手机的函数返回值为 00,然后两台手机都继续执行程序。(请注意黑体字内容)

初始时,只有一台手机。接着,大佬让手机计算形如这样的表达式:

fork() fork() fork()
其中 是二元运算符,为 && 或者 || 中的一种。例如:

fork() && fork() || fork() && fork() && fork() || fork()
两个运算都是左结合的,且 && 的优先级比 || 高,所以上面的那个表达式相当于:

((fork() && fork()) || ((fork() && fork()) && fork())) || fork()
对于表达式 a && b,手机会先计算 a 的值,如果为 00 那么不计算 b 的值(因为很重要所以说两遍,请注意这里不计算 b 的值),该表达式值为 00;否则计算 b 的值并将其值作为该表达式的值。

对于表达式 a || b,手机会先计算 a 的值,如果为 11 那么不计算 b 的值(因为很重要所以说两遍,请注意这里不计算 b 的值),该表达式值为 11;否则计算 b 的值并将其值作为该表达式的值。

表达式计算完成后,大佬制造出了数量惊人的手机,人类终于叩开了指数级工业制造的大门。

一万万年后,一位考古学家调查了此次事件。他得到了大佬让手机计算的表达式。他想知道大佬当年究竟制造出了多少台手机。(包括初始的那台手机)


输入格式

第一行一个正整数 nn,表示表达式中的 fork() 的数量。

接下来一行 n?1n?1 个用空格隔开的字符串,每个字符串为 “&&” 或者 “||”,依次表示表达式中对应位置的运算符。


输出格式

一行,一个整数表示制造出的手机的数量,你只用输出答案对 998244353998244353(7×17×223+17×17×223+1,一个质数)取模后的结果。

解题思路

找规律可以发现,只有$表达式的话,fork()会产生3台手机,fork()$fork()会产生4台手机,fork()$fork()$fork会产生5台手机……依次类推。
那么我们可以用|把若干个连续的$块分割开,每个长度为x的$块会产生x?1个结果为0的表达式,1个结果为1的表达式,那么我们可以从右边往左边递推,假设共tot个$块,可以得到f[i]=[i,tot]段$块产生的手机个数,容易得到DP方程:

f[i]=(num[i]?1)f[i+1]+1,num[i]=第i段连续的$的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<cstdlib>
#include<bitset>
#include<iomanip>
#define LL long long
using namespace std;
const int mod=998244353;
int n,cnt,k;
long long sum;
char a[100005];
int ans0[100005],ans1[100005];
int main ()
{

//freopen ("phone.in","r",stdin);
//freopen ("phone.out","w",stdout);
scanf ("%d",&n);
ans0[0]=1;ans1[0]=1;
for (int i=1;i<=n-1;i++)
{
scanf ("%c%c%c",&a[i],&a[i],&a[i]);
if (a[i]=='&')
cnt++;
else
{
k++;
ans0[k]=cnt+1;
ans1[k]=1;
cnt=0;
}
}
ans0[++k]=cnt+1;
ans1[k]=1;
for (int i=1;i<=k;i++)
{
sum=(sum+(LL)ans1[i]*ans0[i-1]%mod)%mod;
ans0[i]=(LL)ans0[i]*ans0[i-1]%mod;
}
sum=(sum+ans0[k])%mod;
printf ("%lld",sum);
return 0;
}

Markdown

最近的文章

第K小数

题目描述 有两个正整数数列,元素个数分别为N和M。从两个数列中分别任取一个数相乘,这样一共可以得到NM个数,询问这NM个数中第K小数是多少。 输入格式 输入文件名为number.in。输入文件包含三行。第一行为三个正整数N,M和K。第二行为N个正整数,表示第一个数列。第三行为M个正整数,表述第二个 …

于  二分答案 继续阅读
更早的文章

Chess

传送门题目描述 車是中国象棋中的一种棋子,它能攻击同一行或同一列中没有其他棋子阻隔的棋子。一天,小度在棋盘上摆起了许多車……他想知道,在一共N×M个点的矩形棋盘中摆最多个数的車使其互不攻击的方案数。他经过思考,得出了答案。但他仍不满足,想增加一个条件:对于任何一个車A,如果有其他一个車B在它的上方( …

于  组合数 继续阅读