P6424 [COCI2008-2009#2] SETNJA

wheneveright · 2021-10-28 09:54:08 · 题解

link P6424 [COCI2008-2009#2] SETNJA。

解析

对于每个点上的移动情况总共只有三种类型：

• P：显然没有变化，continue 即可；
• L: 向左走，那么方案数乘二；
• R: 向右走，那么方案数在乘二的基础上还要加上叶子节点上的可能性；
• *: 任何都行，那么就是向左的方案数 + 向右的方案数 + 原地不动的方案数，同时因为出现了三种走法，所以叶子节点上的方案数要乘三。

显然会爆 long long，所以要用高精度。实现见代码即可。

代码

因为要用到高精度所以用 python 写了。

在代码中 per 代表叶子节点的情况数量。

s = str (input ())
per = 1
ans = 1
for i in s :
    if i == 'L' :
        ans = ans * 2
    if i == 'R' :
        ans = ans * 2 + per
    if i == '*' :
        ans = ans * 5 + per
        per *= 3
print (ans)