| Online Judge | Online Exercise | Online Teaching | Online Contests | Exercise Author |
|
F.A.Q Hand In Hand Online Acmers |
Best Coder beta VIP | STD Contests DIY | Web-DIY beta |
度度熊与运算式 2
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 166 Accepted Submission(s): 44
Problem Description
某天度熊发现了一个由 $n+1$ 个数字 $1$ 组成的算式如下：
1 $op_1$ 1 $op_2$ 1 $\ldots$ 1 $op_n$ 1
其中 $op_i$ 可能是 `+` (加法运算符号) 或是 `?`。
例如当 $n=5$ 时，式子可能长成这样：`1+1?1+1?1?1`
现在，度熊想把所有的 `?` 取代为 $+$ 或 $\oplus$ (按位异或运算)。
(贴心提示： 加法运算的优先级比按位异或运算还高)
请问取代完后此运算式可能的最大运算结果为何？同时度熊也想知道，有多少取代方式能达到最大的运算结果?
对于两种取代方式，只要存在至少一个 $i$ 使得 $op_i$ 是问号且在两种取代方式被取代为不同运算符号，就视为不同。
1 $op_1$ 1 $op_2$ 1 $\ldots$ 1 $op_n$ 1
其中 $op_i$ 可能是 `+` (加法运算符号) 或是 `?`。
例如当 $n=5$ 时，式子可能长成这样：`1+1?1+1?1?1`
现在，度熊想把所有的 `?` 取代为 $+$ 或 $\oplus$ (按位异或运算)。
(贴心提示： 加法运算的优先级比按位异或运算还高)
请问取代完后此运算式可能的最大运算结果为何？同时度熊也想知道，有多少取代方式能达到最大的运算结果?
对于两种取代方式，只要存在至少一个 $i$ 使得 $op_i$ 是问号且在两种取代方式被取代为不同运算符号，就视为不同。
Input
有多组询问，第一行包含一个正整数 $T$ 代表有几组询问，接着每组测试数据占一行，包含一个长度为 $n$ 的字符串，仅由 `+` 和 `?` 组成，第 $i$ 个字符就是 $op_i$。($n$ 的值不会在数据中出现，请由字符串长度来判断。)
* $1 \le n \le 2^{21}-2$
* 所有询问的 $n$ 的总和不超过 $2 \times 10^7$
* $1 \le n \le 2^{21}-2$
* 所有询问的 $n$ 的总和不超过 $2 \times 10^7$
Output
对于每一个询问输出一行包含两个数字以恰一个空白做分隔，第一个数字代表最大的可能运算结果，第二个数字代表有多少种不同取代方式可以达到相同结果。由于答案可能很大，请输出答案除以 $10^9+7$ 的余数。
Sample Input
6 ? ?? +? ??? ?????????+???? ??????????????
Sample Output
2 1 3 3 3 2 4 1 15 66 15 75 Note 样例的第一组询问算式为：`1?1`。取代后有 $2$ 可能 $1+1$ 和 $1\oplus1$，其中 $1+1=2$、$1\oplus1=0$，所以最大的可能值是 $2$ 且只有一种取代方式能达到该值。 样例的第二组询问算式为：`1?1?1`。取代后有 $4$ 种可能 $1+1+1$,$1+1\oplus1$,$1\oplus1+1$ 和 $1\oplus1\oplus1$，其中 $1+1+1=1+1\oplus1=1\oplus1+1=3$、$1\oplus1\oplus1=1$，所以最大的可能值是 $3$ 且有 $3$ 种取代方式能达到该值。
Source
| Home | Top |
Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-11-22 09:32:57, Gzip enabled |
Administration |