[ROIR 2021] A+B (Day 2)

Luogu
IDLGP9768
Time1000ms
Memory128MB
DifficultyP5
2021ROIR(俄罗斯)
有三个长为 $n$ 的可能含前导零的整数 $a,b,c$,按如下方式排成三行 $n$ 列: ``` a b c ``` 问有多少种不同的**列**的排列方式,使得被横着念出来的三个整数 $x,y,z$ 有 $x+y=z$ 成立且三个整数均没有前导零。 排列方式的个数可能很多,输出其 $\bmod \ 10^9+7$ 即可。 ## Input 第一行为一个长 $n$ 的整数 $a$。 第二行为一个长 $n$ 的整数 $b$。 第三行为一个长 $n$ 的整数 $c$。 ## Output 一行一个整数,表示不同的排列方式的个数对 $10^9+7$ 取模的结果。 [samples] ## Background **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day2 T4 [A+B](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day2.pdf)**。 ## Note 【样例解释1】:所有排列方式均可。 【样例解释2】:我们只计算 $10+20=30$,而不计算 $01+02=03$,因为 $03$ 含前导零。 【样例解释3】:显然有 $10121 + 21909 = 32030$ 与 $12101 + 20919 = 33020$ 两种合法等式,但由于有两个相同的列,所以它们都有两种方式得到答案,总方案数为 $2\times 2=4$。 【数据范围】: 对于所有子任务,有 $2\le n\le 2\times 10^5$。 | 子任务编号 |特殊限制| 分值 | | :-: | :-: | :-: | |$1$|$n\le 6$| $7$ | |$2$|$n\le 18$| $14$ | |$3$| $n\le 200$,读入的数字中不含 $0$ | $15$ | |$4$|$n\le 200$| $5$ | |$5$| $n\le 750$,读入的数字中不含 $0$ | $17$ | |$6$|$n\le 750$| $5$ | |$7$|读入的数字中不含 $0$| $20$ | |$8$|无特殊限制| $17$ |
Samples
Input #1
123
123
246
Output #1
6
Input #2
01
02
03
Output #2
1
Input #3
01211
12099
23300
Output #3
4
Input #4
121
214
999
Output #4
0
API Response (JSON)
{
  "problem": {
    "name": "[ROIR 2021] A+B (Day 2)",
    "description": {
      "content": "有三个长为 $n$ 的可能含前导零的整数 $a,b,c$,按如下方式排成三行 $n$ 列: ``` a b c ``` 问有多少种不同的**列**的排列方式,使得被横着念出来的三个整数 $x,y,z$ 有 $x+y=z$ 成立且三个整数均没有前导零。 排列方式的个数可能很多,输出其 $\\bmod \\ 10^9+7$ 即可。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9768"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有三个长为 $n$ 的可能含前导零的整数 $a,b,c$,按如下方式排成三行 $n$ 列:\n\n```\na\nb\nc\n```\n问有多少种不同的**列**的排列方式,使得被横着念出来的三个整数 $x,y,z$ 有 $x+y=z$ 成立且三个整数均没有前导零。\n\n排列方式的个数可能很多,输出其 $\\bmod \\ 10^9+7$ 即可。\n\n## Input\n\n第一行为一个长 $n$ 的整数 $a$。\n\n第二...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments