2025年1018 Subnumbers (35)（35 分）

科技前沿 • 2025-01-06 14:15 • 阅读 48

大家好，我是讯享网，很高兴认识大家。

1018 Subnumbers (35)（35 分）
Given a positive integer N, let us define a “subnumber” of N as a consecutive number of digits NOT starting with 0. For example if N = 1021, it has 7 subnumbers, namely, 1, 10, 102, 1021, 2, 21 and 1 (again). Here is your task: please calculate the sum of all the subnumbers of N. For 1021, the sum is 1+10+102+1021+2+21+1 = 1158. Since the result may be very large, output the answer modulo (10⁹

please.
Input Specification:

Each input file contains one test case, which gives the integer N (0 < N < 10) in a line.

Output Specification:

Print in a line the sum of all N’s subnumbers (modulo ).

Sample Input:

对于一个数，考虑它对res的贡献
这里写图片描述
统计一下每个数的前缀和（突然想到好像只要统计一次10^0加到10N的和，然后可以乘每个数就行了。多开了十倍的空间。。。。。。）
然后统计一下前缀非0数的个数，搞一下就行了。
代码如下

#include <bits/stdc++.h> using namespace std; #define N (int)1e5+10 char arr[N]; typedef long long ll; ll pre[10][N]; int pren[N]; const int mod = ; void init() { ll i, j; for (i = 1; i <= 9; i++) { pre[i][0] = i; for (j = 1; j < N; j++) { pre[i][j] = (pre[i][j-1] * 10) % mod + i; } } } int main(void) { init(); scanf("%s", arr+1); ll res = 0; int i; int len = strlen(arr+1); pren[0] = -1; for (i = 1; i <= len; i++) { if (arr[i] != 48) pren[i] = pren[i-1]+1; else pren[i] = pren[i-1]; } for (i = 1; i <= len; i++) { if (arr[i] == 48) continue; res = (res + pre[arr[i]-48][len-i]*(pren[i]+1)) % mod; } cout << res; }

讯享网

2025年1018 Subnumbers (35)（35 分）

相关推荐