307599: CF1380F. Strange Addition

Memory Limit:256 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Strange Addition

题意翻译

## 题目描述 对于非负整数 $a,b$,定义它们的 "奇异加法 $\oplus$" 如下: 1. 将 $a,b$ 一上一下写在两行,并按照低位对齐。 2. 将它们的每一位加起来,并将**每一位的结果从高位到低位连接在一起**,得到的就是 $a\oplus b$。 (你可以认为,两个数都有无穷多的前导 0) 例如,$3248\oplus 908=311416$,因为: ![3248+908=311416](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1380F/a527f267dad59d6e6b988913627229dffe969f7d.png) 你现在有一个**仅包含 $n$ 个 $0\sim 9$ 的数码**的字符串 $c$,并且还有 $m$ 次操作。一次操作为: - ```x d``` - 将 $c$ 的第 $x$ 个数码替换成数码 $d$ 。 (注意,$c$ 在任何时刻都可能存在前导 0) 每次操作过后,你需要输出,有多少个**有序对** $(a,b)$,满足 $a,b$ 都是非负整数,且 $a\oplus b=c$。 答案对 $998244353$ 取模。 ## 输入格式 第一行输入两个整数 $n,m$ ( $1\le n,m\le 5\cdot 10^5 $) ,表示 $c$ 的长度和操作次数。 第二行输入 $c$,$c$ 包含 $n$ 个 $0\sim 9$ 的数码。 接下来的 $m$ 行,每行输入两个整数 $x,d$ ( $1\le x\le n,0\le d\le 9$ ) ,表示一次操作。 ## 输出格式 输出共 $m$ 个整数。第 $i$ 个整数表示在前 $i$ 次操作后,有多少个有序对 $(a,b)$ ,满足 $a,b$ 为非负整数且 $a\oplus b=c$ (对 $998244353$ 取模)。 ## 样例解释 第一次操作后 $c$ 为 $14$,此时满足条件的 $(a,b)$ 有:$(0,14),(1, 13),(2, 12),(3, 11),(4, 10),(5, 9),(6, 8),(7, 7),(8, 6),(9, 5)(10, 4),(11, 3),(12, 2),(13, 1),(14, 0)$ 第二次操作后 $c$ 为 $11$。第三次后 $c$ 为 $01$ 。

题目描述

Let $ a $ and $ b $ be some non-negative integers. Let's define strange addition of $ a $ and $ b $ as following: 1. write down the numbers one under another and align them by their least significant digit; 2. add them up digit by digit and concatenate the respective sums together. Assume that both numbers have an infinite number of leading zeros. For example, let's take a look at a strange addition of numbers $ 3248 $ and $ 908 $ : ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1380F/a527f267dad59d6e6b988913627229dffe969f7d.png)You are given a string $ c $ , consisting of $ n $ digits from $ 0 $ to $ 9 $ . You are also given $ m $ updates of form: - $ x~d $ — replace the digit at the $ x $ -th position of $ c $ with a digit $ d $ . Note that string $ c $ might have leading zeros at any point of time. After each update print the number of pairs $ (a, b) $ such that both $ a $ and $ b $ are non-negative integers and the result of a strange addition of $ a $ and $ b $ is equal to $ c $ . Note that the numbers of pairs can be quite large, so print them modulo $ 998244353 $ .

输入输出格式

输入格式


The first line contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 5 \cdot 10^5 $ ) — the length of the number $ c $ and the number of updates. The second line contains a string $ c $ , consisting of exactly $ n $ digits from $ 0 $ to $ 9 $ . Each of the next $ m $ lines contains two integers $ x $ and $ d $ ( $ 1 \le x \le n $ , $ 0 \le d \le 9 $ ) — the descriptions of updates.

输出格式


Print $ m $ integers — the $ i $ -th value should be equal to the number of pairs $ (a, b) $ such that both $ a $ and $ b $ are non-negative integers and the result of a strange addition of $ a $ and $ b $ is equal to $ c $ after $ i $ updates are applied. Note that the numbers of pairs can be quite large, so print them modulo $ 998244353 $ .

输入输出样例

输入样例 #1

2 3
14
2 4
2 1
1 0

输出样例 #1

15
12
2

说明

After the first update $ c $ is equal to $ 14 $ . The pairs that sum up to $ 14 $ are: $ (0, 14) $ , $ (1, 13) $ , $ (2, 12) $ , $ (3, 11) $ , $ (4, 10) $ , $ (5, 9) $ , $ (6, 8) $ , $ (7, 7) $ , $ (8, 6) $ , $ (9, 5) $ , $ (10, 4) $ , $ (11, 3) $ , $ (12, 2) $ , $ (13, 1) $ , $ (14, 0) $ . After the second update $ c $ is equal to $ 11 $ . After the third update $ c $ is equal to $ 01 $ .

Input

题意翻译

## 题目描述 对于非负整数 $a,b$,定义它们的 "奇异加法 $\oplus$" 如下: 1. 将 $a,b$ 一上一下写在两行,并按照低位对齐。 2. 将它们的每一位加起来,并将**每一位的结果从高位到低位连接在一起**,得到的就是 $a\oplus b$。 (你可以认为,两个数都有无穷多的前导 0) 例如,$3248\oplus 908=311416$,因为: ![3248+908=311416](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1380F/a527f267dad59d6e6b988913627229dffe969f7d.png) 你现在有一个**仅包含 $n$ 个 $0\sim 9$ 的数码**的字符串 $c$,并且还有 $m$ 次操作。一次操作为: - ```x d``` - 将 $c$ 的第 $x$ 个数码替换成数码 $d$ 。 (注意,$c$ 在任何时刻都可能存在前导 0) 每次操作过后,你需要输出,有多少个**有序对** $(a,b)$,满足 $a,b$ 都是非负整数,且 $a\oplus b=c$。 答案对 $998244353$ 取模。 ## 输入格式 第一行输入两个整数 $n,m$ ( $1\le n,m\le 5\cdot 10^5 $) ,表示 $c$ 的长度和操作次数。 第二行输入 $c$,$c$ 包含 $n$ 个 $0\sim 9$ 的数码。 接下来的 $m$ 行,每行输入两个整数 $x,d$ ( $1\le x\le n,0\le d\le 9$ ) ,表示一次操作。 ## 输出格式 输出共 $m$ 个整数。第 $i$ 个整数表示在前 $i$ 次操作后,有多少个有序对 $(a,b)$ ,满足 $a,b$ 为非负整数且 $a\oplus b=c$ (对 $998244353$ 取模)。 ## 样例解释 第一次操作后 $c$ 为 $14$,此时满足条件的 $(a,b)$ 有:$(0,14),(1, 13),(2, 12),(3, 11),(4, 10),(5, 9),(6, 8),(7, 7),(8, 6),(9, 5)(10, 4),(11, 3),(12, 2),(13, 1),(14, 0)$ 第二次操作后 $c$ 为 $11$。第三次后 $c$ 为 $01$ 。

加入题单

上一题 下一题 算法标签: