初等数论杂谈三 - “空山新雨后”
2026-07-19 10:32:36
发布于：浙江
自主学习笔记类产物
“空山新雨后，天气晚来秋。”——王维《山居秋暝》
——————————————————————————————————————————
杂谈二塞不下了。但是还有一堆题目。
https://www.luogu.com.cn/problem/P1287
01串
这个题还行。但是我写的时候好像降智了，让我把代码抱出来放置以下。
注释不一定对。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int NN=40;
int F[NN][NN];
int N,L,I,sum;
int d[NN];//当前位置放什么？
void p(int x){
//对于当前的第x位，我们需要枚举放0还是放1
if(x>N)return;
if(L==0){//当没有一可以放，我们就必须放零
d[x]=0;
return;
}
//枚举放1
int if1=F[N-x][L-1]; //假设现在要放一，那么我们需要查看这个位置放置一后，我们有多少种串
//由于我们的目标是第I种串，所以我们要判断它的串数量是否能够囊括I
//I是从小到大的，我们需要继而计算if0，而不是只计算if1
int if0=F[N-x][L];
//cout<<N-x<<" "<<L<<" "<<if1<<" "<<if0<<'\n';
if(if0>=I){
d[x]=0;
p(x+1);
return;
}
d[x]=1;
//并且我们还要把1减掉一个
L--;
I-=if0;
p(x+1);
}
int C(int n,int m){
int ans=1;
for(int i=1;i<=m;i++)ans=ans*(n-m+i)/i;
return ans;
}
signed main(){
cin>>N>>L>>I;
//长度为N的01串，最多只能放置L个1，询问从小到大排序的第I个01串
//计算F[i][j]：F[i][j]代表当有i个位置，可以放置j个1，有多少种串串
//本板块应该没问题
for(int i=1;i<=N;i++){
for(int j=0;j<=L;j++){
F[0][j]=1;
F[i][j]=0;
for(int k=0;k<=j;k++){
F[i][j]+=C(i,k);
}
}
}
p(1);
for(int i=1;i<=N;i++){
cout<<d[i];
}
return 0;
}
我先来写一下这道题目的大致思路：
因为它说是要找“从小到大排序的第I个01串”嘛。能够想到“1”排在越前面，这个01串就越大。
当时我的初步思路是：
它其实已经比较接近正解了。
差在哪里呢？不够详细（这不仅仅是我没写，而是我的代码实现还是有差距，我写不出来）
所以我们这里主要来看看这段代码是如何实现的：
void p(int x){
if(x>N)return;
if(L==0){
d[x]=0;
return;
}
int if1=F[N-x][L-1];
int if0=F[N-x][L];
if(if0>=I){
d[x]=0;
p(x+1);
return;
}
d[x]=1;
L--;
I-=if0;
p(x+1);
}
我们在这里计算“目前位选择填一”和“目前位选择填零”的方案数分别是多少。
如果说，I是被包含在“目前位置选择填零”的方案数中的，那么我们就直接选择在当前位置填写零。
如果它没有被包含在选零的方案数（也就是说它需要更大的数字，此时我们就没有办法继续在这一位上填写零，要不然它就太小了），那我们就选一（选一需要将L减掉，而且需要让I减掉if0（因为它已经在右半边了））
还有一个非常重要的点：
F[0][j]=1;
这是一个卡掉了我的点。注意到我们是需要的初始化的。
因为是会等于的。我们来看一个神奇的反例：
输入：4 2 1
输出：0000
如果不加的初始化，它就会输出：
因为If0<1
（空串也是串）
https://www.luogu.com.cn/problem/P5520
青原樱 我做是因为名字好听
本题的大概意思就是：一共有n个空位，m颗互不相同的树苗。树苗种下去后其左右两个空位不能再种树苗。问有多少种方法把所有的树苗都种了。
但是这道题我的思路其实是偏离正确思路的，后面看了题解才补掉。
我们直接写正解吧。
已知我们有m颗树苗，m颗树苗需要m-1个空位，我们先把这m-1个空位拿出来。
现在我们剩下了n-m+1个空位，我们可以随意地把树苗种在里面。
所以答案是
最后按着这个乘出来就好了：
总结：
1.几句话概括城市建设思路
一个不上升序列和一个不下降序列本质上可以用相同的计算方式。抛弃x和y，一个序列的计算方式是：。计算x和y相同的情况则需要分类讨论（分类讨论的主要是x和y分别在前后序列的情况名单时它们最终的处理方式其实是完全相同的，所以我只写一个）当x摆在一个位置上且数值为h序列又要求单调性的时候，它前面的1~x-1个数的值域就是[1,h]；它后面的数的值域就是[h,m]此时我们单独计算它前面的和后面的方案书，最后将前后相乘即可。
2.几句话概括01串思路
本题的思路还算是比较简单。挨个枚举每一位上是一还是零：如果放置零的方案书已经足够囊括I，那么直接选择放零即可；如果不够，那我们选择放1，且I-=放一的方案数，能够放置的一的数量减一。
这边我们需要先预处理出来放零放一的方案数。记得空串也是串。
3.几句话概括青原樱思路
虽然花不同，但是空格相同。我们可以像城市建设一样，把个空格挑出来（到时候假装它自己会回去），然后剩下的空格就可以随意放花了，所以最后的答案是：
接下来，我来把昨天的斯特林数重新翻炒一下。
斯特林数：要求一个含有n个A和个B的数列在任何时候（每个前缀）所包含的A的数量必须大于B的数量的序列的方案书。
斯特林数有两种求法：
1.
2.
——————————————————————————————————————————
https://www.luogu.com.cn/problem/P1287
盒子与球
其实我觉得这题并不简单（碎碎念）
一开始在往插板法（？）的方向想。但实际上它应该是一道容斥。
先说容：我们现在先把所有的方案都算出来。
当允许空盒，那么方案书应该是（每一个球都有m种方案）
再说斥：有k个空盒的计算式是：
那么我们可以减一个空盒的方案数，加两个空盒的方案数，减三个空盒的方案数，加四个空盒的方案数balabala
也就是说，我们可以得到一个这样的式子：
将它进行一些揉搓:
再进行一些揉搓：
完成啦！
然后不需要逆元不需要特殊方法去完成组合数计算。
代码简单，不想写了。
好吧还是写一下。好歹是题目。
跳了一会儿发现是快速幂又写错了破大防，怒写快速幂。
这里空空如也
有帮助，赞一个