当前位置: 首页 > news >正文

CF520E Pluses everywhere 题目分析

题目概述

给定一个 \(n\) 位的十进制数,可以在数字之间加恰好 \(k\)+,得到一个式子,求每种方案的这个式子的和。

\(10^9+7\) 取模,数据范围:\(1\leq n\leq 10^5\)

分析

有点意思。

不难想到设 \(f_{i,j}\) 表示前 \(i\) 个数填 \(j\) 个加号的方案和,转移是简单的,考虑在不在前面放 + 即可。

但是这不是本题的思路。

像这种求所有的全局的方案,一般考虑每一个位置对于总共答案的贡献是多少。

我们考虑从前往后的第 \(i\) 个位置,这个数填在当前分割出来的数的从前往后数第 \(j\) 位,显然 \(j\leq n - i + 1\)

那么对于当前他的数值方面的贡献为 \(a_i\times 10^j\),那么它的方案为 \(C_{n-1-(j-1)-1}^{k-1}=C_{n-j-1}^{k-1}\)

为什么是这个组合数?

\(n-1\) 是我们可选的位置,后面再 \(-1\) 是因为肯定所分割出来的数的后面有一个加号,再加上其长度为 \(j\),因此占有 \(j-1\) 个位置不能填 + 号。

那么这就引申出一个问题,当我的 \(j=n-i+1\) 时,那么我的后面是填不了 + 号的,因此此时方案为 \(C_{n-1-(j-1)}^{k}=C_{n-j}^k\)

形式化地讲就是:

\[\sum_{i=1}^n\left(10^{n-i+1}\times a_i\times C_{i-1}^{k}+\sum_{j=1}^{n-i}10^j\times a_i\times C_{n-j-1}^{k-1}\right) \]

我们注意到后面的组合数跟 \(i\) 无关,考虑先枚举 \(j\),有:

\[\sum_{j=1}^n\left(a_{n-j+1}\times 10^j\times C_{n-j}^{k}+C_{n-j}^{k-1}\sum_{i=1}^{n-j}a_i\right) \]

显然后面那一个求和是可以前缀和优化的。

代码

时间复杂度 \(\mathcal{O}(n)\)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define int long long
#define N 100005
using namespace std;
const int mod = 1e9 + 7;
int jc[N],inv[N],sum[N],a[N];
int C(int a,int b) {if (a < 0 || b < 0 || a < b) return 0;return jc[a] * inv[b] % mod * inv[a - b] % mod;
}
signed main(){jc[0] = jc[1] = inv[0] = inv[1] = 1;for (int i = 2;i < N;i ++) jc[i] = jc[i - 1] * i % mod,inv[i] = (mod - mod / i) * inv[mod % i] % mod;for (int i = 2;i < N;i ++) inv[i] = inv[i - 1] * inv[i] % mod;int n,k;scanf("%lld%lld",&n,&k);for (int i = 1;i <= n;i ++) {char x;cin >> x;a[i] = x - '0';sum[i] = sum[i - 1] + a[i];}int ans = 0;for (int i = 1,t = 1;i <= n - k;i ++,t = t * 10 % mod) {ans = (ans + t * a[n - i + 1] % mod * C(n - i,k) % mod) % mod;ans = (ans + t * sum[n - i] % mod * C(n - i - 1,k - 1) % mod) % mod;}cout << ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=15064

相关文章:

  • java里面的IO流分为哪几种,他们的区别是什么呢
  • ReLU函数及它的导数
  • 基础数论
  • 第一次个人编程作业-论文查重
  • 使用Claude代码子代理生成项目特定提交消息的技术实践
  • 走迷宫(BFS)
  • MyBatis分页的原理和分页插件的原理是什么
  • 达成度报告
  • 旋转图像-leetcode
  • 【ChipIntelli 系列】ASR部分——合成语言模型和多网络(多语种)切换
  • 内网环境怎么安装软件(用 yum / apt 下载离线包并搬入内网)
  • tanh函数
  • P13617 [ICPC 2024 APC] Bit Counting Sequence
  • 打一局吗(60pts 解法)
  • 软工9.23
  • 本地部署qwen-0.6b
  • 25分钟小练习
  • 第七章 手写数字识别V2
  • 常用软件下载
  • 实用指南:S 4.1深度学习--自然语言处理NLP--理论
  • PyTorch图神经网络(五)
  • java
  • Jordan块新解
  • [CSP-S 2024] 染色
  • Kerberos 安装和使用
  • 第一次个人编程任务
  • 概率期望总结
  • redis实现秒杀下单的业务逻辑
  • 关于边缘网络+数据库(1)边缘网络数据库模式及选型