计数题目题解_牛客竞赛OJ

yunayu

发表于 2026-01-29 04:30:22

我爱数学！我爱数学！我爱数学！从前有一位老师说，如果你想学好一个学科，只需要每天早上醒来，大喊三遍你爱它。所以说，数学到底是什么呢？一路走来，她不断变换着样子。从前，她作为一门学科，伴随我们走完完整的学生时代。现在，她化为算法竞赛中的一个板块，藏匿在一道道题目描述中,等待着我们的造访。我常认展开全文

腌萝卜干

发表于 2026-01-29 11:16:44

思路发现只需要将所有的空段找出来, 分别计算贡献假设对于当前空段, 长度是, 可以填的数字数量是假设对于数字填了个, 数字填了个... 那么有发现每个, 将其转化, 得到新的这样就可以利用隔板法计算组合数, 要求将球的数量分为堆, 放置个隔板方案数是计算组合数可以用乘法逆元优化实展开全文

pandaC222

发表于 2026-01-29 14:30:44

我讨厌数学，一道组合数的题 #include<bits/stdc++.h> using namespace std; #define int long long const int INF = 0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const 展开全文

怎么不AC啊

发表于 2026-01-29 06:59:21

题目目标在于找到各个连续0序列，算出计数贡献后乘起来。因此，核心的任务在于，对于一个[l,0,0,...,0,r]的序列，如何求出其计数贡献。我们将0的个数记为，形式化地，问题为：个数的数列满足以下表达式，求符合的数量这个事情的需求有两个：单调不减整个数列在内如果我们要手动展开全文

只会啊吧啊吧

发表于 2025-10-12 15:51:23

题目主要是计算组合数。当遇到0时，我们先统计一共有多少连续的0，cnt个。然后用提前维护的前缀最小值（除0外），后缀最大值（除0外），我们可以得到这串0的取值范围[maxa_i, mina_i]。根据组合数学，从 n 个元素中可重复选取 m 个元素的选法数量为组合数 C (n + m - 展开全文

YunBaichuan

发表于 2026-01-29 11:34:45

参考：https://blog.nowcoder.net/n/524adc66d6b04d149d89b0ce79b93c0b 思路：组合数学结论。本题主要就是这个结论，如果你不知道的话，基本上写不出来了。这个结论其实是隔板法的推论：对于m个数中可重复的选取n个数，方案数有comb(m + n - 展开全文

此在Dasein

发表于 2026-01-29 05:34:31

基于组合数学的线性计数模型 1. 问题分析本题是一个典型的受限序列填充计数问题。我们需要在保证序列单调不增（Monotonically Non-Increasing）的前提下，计算填充所有缺失位置（0）的方案数。可以将问题分解为以下几个关键特征：锚点分割（Segmentation by An 展开全文

BeauWill

发表于 2026-01-29 11:23:37

C++的自动取模类Z和组合数comb用的jiangly鸽鸽的模板，具体实现可以看后面的Python代码 #include <iostream> #include <vector> #include <cassert> using i64 = long long; 展开全文

imitater

发表于 2026-01-29 14:48:48

#include <bits/stdc++.h> #include <unistd.h> using namespace std; typedef long long LL; const int N=1.1e6+10,P=1e9+7; LL n,fac[N],ifac[N]; 展开全文

牛客937992666号

发表于 2026-01-29 14:49:23

将修改为到的数字，求有多少种不递增序列举一些例子后，发现解决这道题目的核心就是求：现在有连续为的长度为，然后可以填写的数字有个，求有多少种方案可以填写的数字有个，化简为能填写. 使用隔板法求求方案数：现在需要填写的格子有，可以填写的数字有个。设表示数展开全文

相关比赛

等你来战