| 题目名称 | 1704. [NEERC2003]平凡的车票 |
|---|---|
| 输入输出 | banal.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 50 |
| 题目来源 |
 cstdio
于2014-09-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：6， 通过率：16.67% | ||||
 cstdio |
100 | 2.698 s | 26.67 MiB | C++ |
 mikumikumi |
98 | 9.599 s | 1.73 MiB | C++ |
|
mikumikumi |
98 | 10.335 s | 1.70 MiB | C++ |
 夜雨 |
74 | 4.028 s | 22.26 MiB | C++ |
|
夜雨 |
56 | 4.048 s | 22.26 MiB | C++ |
|
mikumikumi |
0 | 15.263 s | 1.69 MiB | C++ |
| 关于 平凡的车票 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
高精+hash+状态压缩DP一次写对，今天RP真是好……
| ||||
【题目描述】
Peter喜欢数论。因此他正在寻找有趣的车票。号码长度为2N的车票是“有趣的”当且仅当其前N位数码的乘积等于后N位数码的乘积。其他车票都是平凡的。
Peter在他的钱包里找到了一张用过的车票。不幸的是这张票已经被打了孔，因此Peter无法识别一些数码。他想要知道这张车票是否有趣。而且他还想知道有多少种有趣的车票可以在打孔后变成这一张。
帮助Peter找到这个问题的答案。
【输入格式】
第一行有一个整数N（1<=N<=18），第二行有一个字符串，代表车票号码。‘?’代表被打孔的数字。
【输出格式】
第一行输出（打孔后能变成这张车票的）有趣的车票数。第二行输出无趣的车票数。
【样例输入】
2 2??3
【样例输出】
4 96
【来源】
Northeastern Europe 2003,Northern Subregion