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

[NOIP 2016 提高组] 组合数问题

我们先考虑暴力,暴力枚举每一个\(i,j\)暴力算\(\binom{i}{j}\)
时间复杂度为\(O(T*N^3)\),显然超时

然后我们发现\(N,M \le2000\)
我们考虑使用组合数的递推公式预处理\(\binom{0}{0}\)\(\binom{2000}{2000}\)

这里说一下组合数递推公式\(\binom{i}{j}=\binom{i-1}{j-1}+\binom{i-1}{j}\)
可以从组合意义上来理解 我们从\(i\)个数中选\(j\)个数,对于每一个数可以分为选与不选两种情况,选的时候即\(\binom{i-1}{j-1}\),在剩下的\(i-1\)个数里选\(j-1\)个数,不选的时候即\(\binom{i-1}{j}\),在剩下的\(i-1\)个数里选出\(j\)个数.

但是这样复杂度为\(O(T*N^2+N^2)\),依旧无法通过,事实上我们需要一种不需要枚举\(i,j\)的方法才能通过。

我们发现对于多个询问,\(k\)始终为定值,于是考虑前缀和优化,设\(ans_{i,j}\),在预处理时,若\(k|\binom{i}{j}\),则将\(ans_{i,j}+1\)。然后套用二维前缀和。但是我们发现,二维前缀和递推时 \(ans_{i,j}=ans_{i-1,j}+ans_{i,j-1},-ans_{i-1,j-1}+[k|\binom{i}{j}]\),在处理到边界时,我们会用未处理的值(因为此时\(i<j\))来更新。
但是我们又发现

对于所有的 \(0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )\) 有多少对 \((i,j)\) 满足 \(k|\binom{i}{j}\)

于是我们直接将未处理的值设为同一行上一个值

由此即可AC这道题了!

点我展开看代码
```cpp#include <bits/stdc++.h>using namespace std;#define int long longint t,n,m,k,c[2008][2008],ans[2008][2008];void init(){c[0][0]=1;c[1][0]=c[1][1]=1;for(int i=2;i<=2000;i++){c[i][0]=1; for(int j=1;j<=i;j++){c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];if(c[i][j]==0){ans[i][j]++;} }ans[i][i+1]=ans[i][i]; }}signed main(){cin>>t>>k;init(); while(t--){cin>>n>>m;if(n<m){cout<<ans[n][n]<<"\n";} else{cout<<ans[n][m]<<"\n"; }}return 0;}
```
http://www.hskmm.com/?act=detail&tid=21733

相关文章:

  • 新建第一个项目
  • 笛卡尔树 (区间最小值)
  • CF2003F. Turtle and Three Sequences
  • 【Rust GUI开发入门】编写一个本地音乐播放器(11. 支持动态明暗主题切换) - Jordan
  • 利用接口中的静态虚拟成员实现自定义配置节
  • 天线增益与有源接收面积之间的关系
  • 2025CSP-S晋级和英才计划入围后:我走过了哪些路
  • 流量分析
  • fdsaf -
  • 【J+S 二十连测】-- 第十二套爆炸记
  • 2025-2026-1 CS3311 软件工程 个人项目第一版已发布
  • Python浅拷贝、深拷贝
  • 破解 Pycharm
  • 阿里业务身份建模
  • 实用指南:矩阵结构体 图片绘制 超级玛丽demo6
  • 5分钟理清:Session、JWT、Token、SSO、OAuth 2.0 认证逻辑
  • 2025年10.1~10.6日信息竞赛计划安排表
  • 【Rust GUI开发入门】编写一个本地音乐播放器(10. 拼装UI组件) - Jordan
  • 国产数据库-达梦docker镜像安装
  • CAP 8.4 版本发布通告
  • 【Leetcode】随笔 - 详解
  • DevEco Studio 编辑器的使用 - 实践
  • docker安装MySQL8.0.25的坑
  • WPF 深入系列.2.布局系统.尺寸属性 - 指南
  • 实训
  • Kosaraju算法
  • bat批处理设置临时PATH路径不能访问
  • 10. Spring AI + RAG - Rainbow
  • 《AI智能体实战研发教程(从0到企业级项目落地)》全网上线|CSDN B站同步首发
  • 9. Spring AI 当中对应 MCP 的操作 - Rainbow