月赛50 F 鸡尾酒数（思维）

鸡尾酒数（思维）"/>

月赛50 F 鸡尾酒数（思维）

登录—专业IT笔试面试备考平台_牛客网牛客网是互联网求职神器，C++、Java、前端、产品、运营技能学习/备考/求职题库，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

定义数位和是一个数字中每一个数位的和，例如数字 123 的数位和是 1+2+3=6，数字 1024 的数位和是 1+0+2+4=7。

鸡尾酒和玥玥的生日连起来是 512417，这个数字的数位和是 5+1+2+4+1+7=20，恰好是 10 的倍数。所以鸡尾酒定义：如果某一个数字的数位和恰好是 10 的倍数，那么我们称它为一个“鸡尾酒数”。

给定 nnn，请问 1∼n1\sim n1∼n （即 111 到 nnn 之间所有整数）这些数字中有多少个鸡尾酒数，由于结果可能很大，请输出答案对 109+710^9+7109+7 取模后的结果。

题目出到这里，鸡尾酒深感这样的难度远远无法满足参与小白玥赛的众位小白之王，于是加入了单点修改的机制。再给定 qqq 次询问，每次询问给出两个数字 a,ba,ba,b，表示将 nnn 的数位中从左往右的第 aaa 位修改为数字 bbb，再问 1∼n1 \sim n1∼n 中有多少个鸡尾酒数。对于每次询问你都需要回答一次这个问题。

请注意：每次询问时的修改都会永久生效；一个数字最左边的一位记为第一位。 

一道很好的思维题，一开始可能会想到数位dp，但后来需要修改某一位的值就要打消这个念头了，思考本题我们需要求出1到n能够数位和能够整除10的数，思考后想出一个结论，如果确定了该数字的前面几位，那么我们一定可以在第一位中凑出一个数使前几位的数位和为10的倍数，那么问题就可以转化为维护n/10和除开个数位上的数位和就行（思考一种情况，如果n=12111，当前4位取为1211时，个位是凑不出6来为10的倍数的，所以还要维护前几位的数位和来判断最后一次是否能取到r,若取不到则-1）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
//const int mod=1e9+7;
const int MAXN = 1e6;
using ll = long long ;
ll n, q;
char s[MAXN];
ll pre[MAXN];
const ll mod = 1e9 + 7;ll check(ll d, ll lst) {if (n == 1 || lst >= 10 - d || d == 0)return 0;return 1;
}int main() {scanf("%s %lld", s + 1, &q);n = (ll)strlen(s + 1);pre[1] = 1;for (int i = 2; i <= n + 5; i++) {pre[i] = pre[i - 1] * 10 % mod;}ll dsum = 0, ans = 0;for (int i = 1; i <= n - 1; i++) {dsum += (s[i] - '0');ans = (ans * 10ll + (ll)(s[i] - '0')) % mod;}printf("%lld\n", (ans - check(dsum % 10, s[n] - '0') + mod) % mod);int a, b;while (q--) {scanf("%d %d", &a, &b);if (a != n) {dsum -= s[a] - '0';ans = (ans - pre[n - a] * (ll)(s[a] - '0') + mod) % mod;}s[a] = (b + '0');if (a != n) {dsum += b;ans = (ans + pre[n - a] *(ll) b) % mod;}printf("%lld\n", (ans - check(dsum % 10, s[n] - '0') + mod) % mod);}return 0;
}