XP04-Day03
2026-08-14 20:53:58
发布于：广东
117阅读
0回复
0点赞
隔板法 至少每个盒子有1个小球
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510, mod = 998244353;
ll C[N][N];
void init(){
C[0][0] = 1;
for(int i=1;i<=500;i++){
C[i][0] = 1;
for(int j=1;j<=i;j++){
C[i][j]=C[i-1][j]+C[i-1][j-1];
}
}
}
int main(){
init();
int n,m;
cin>>n>>m;
cout<<C[n-1][m-1]<<endl;
return 0;
}
隔板法 2 盒子可以没有小球
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1110, mod = 998244353;
ll C[N][N];
void init(){
C[0][0] = 1;
for(int i=1;i<N;i++){
C[i][0] = 1;
for(int j=1;j<=i;j++){
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
}
int main(){
init();
int m,q;
cin>>m>>q;
while(q--){
int k;
cin>>k;
if(m==0){
if(k==0) cout<<1<<endl;
else cout<<0<<endl;
}
else{
cout<<C[m+k-1][m-1]<<endl;
}
}
return 0;
}
杨辉三角求小范围组合数学
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510, mod = 998244353;
ll C[N][N];
void init(){
C[0][0] = 1;
for(int i=1;i<=500;i++){
C[i][0] = 1;
for(int j=1;j<=i;j++){
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
}
int main(){
int q;
cin>>q;
init();
while(q--){
int n,k;
cin>>n>>k;
cout<<C[n][k]<<endl;
}
return 0;
}
分水果
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2010, mod = 998244353;
ll fact[N], infact[N];
ll bpow(ll a, ll k, ll p){
ll res = 1;
while (k){
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
void init(){
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ ){
fact[i] = fact[i - 1] * i % mod;
infact[i] = infact[i - 1] * bpow(i, mod - 2, mod) % mod;
}
}
ll C(int n,int m){
if(m>n||m<0) return 0;
return fact[n] * infact[m] % mod * infact[n - m] % mod;
}
int main(){
int n,m,k;
cin>>n>>m>>k;
init();
ll ans = m * bpow(m-1,k,mod) % mod * C(n-1,k) % mod;
cout<<ans;
return 0;
}
考试T10
#include<bits/stdc++.h>
#define int long long
#define N 500010
using namespace std;
int n,m,op,x,y,a[N],tr[N];
int lowbit(int x){
return x&-x;
}
void update(int x,int y){
for(int i=x;i<=N;i+=lowbit(i)) tr[i]+=y;
}
int query(int x){
int ans=0;
for(int i=x;i>0;i-=lowbit(i)) ans+=tr[i];
return ans;
}
signed main(){
cin>>n>>m;
while(m--){
cin>>op;
if(op==1){
cin>>x>>y;
update(x,1);
update(y+1,-1);
}
else{
cin>>x;
cout<<query(x)%2<<endl;
}
}
return 0;
}
考试T11
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
struct node{
int l,r,id;
}a[N];
int n,b[N];
bool cmp(node x,node y){
return x.r<y.r;
}
int tr[N];
int ans[N];
int lowbit(int x){
return x&-x;
}
void add(int x,int v){
for(int i=x;i<=n;i+=lowbit(i))tr[i]+=v;
}
int sum(int x){
int ans = 0;
for(int i=x;i>0;i-=lowbit(i))ans+=tr[i];
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].l,&a[i].r);
a[i].id = i;
b[i] = a[i].l;
}
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
int idx = lower_bound(b+1,b+n+1,a[i].l) - b;
ans[a[i].id] = sum(n) - sum(idx);
add(idx,1);
}
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
return 0;
}
值域树状数组 + 离散化
树状数组求逆序对
1. 逆序对
满足：
i < j 且 a[i] > a[j]
则 (i,j) 是一对逆序对。
暴力做法：
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(a[i]>a[j]) ans++;
复杂度 O(n²)。
2. 核心思想
从左往右枚举 a[i]。
此时前面共有：
i-1 个数
只需要知道：
前面有多少个数 > a[i]
这些数都能和 a[i] 组成逆序对。
树状数组维护：
前面每个数值出现的次数。
3. 离散化
数据值可能很大，所以先排序去重，把数值变成排名。
例如：
100 20 50 20
变成：
20 → 1
50 → 2
100 → 3
代码：
sort(b+1,b+n+1);
m=1;
for(int i=2;i<=n;i++){
if(b[i]!=b[m]) b[++m]=b[i];
}
查排名：
int idx=lower_bound(b+1,b+m+1,a[i])-b;
4. 树状数组维护什么
update(idx,1);
表示：
排名 idx 的数字又出现了 1 次
因此：
query(idx);
表示：
前面 <= a[i] 的数字数量
而前面总共有：
i-1
所以：
i-1-query(idx)
就是：
前面 > a[i] 的数字数量
也就是当前新增的逆序对。
5. 核心代码
for(int i=1;i<=n;i++){
int idx=lower_bound(b+1,b+m+1,a[i])-b;
ans+=i-1-query(idx);
update(idx,1);
}
一定要：
先查询
再加入
因为我们统计的是前面的数。
7. 记忆
query(idx)
= 前面 <= 当前数的数量
i-1-query(idx)
= 前面 > 当前数的数量
= 当前新增逆序对
核心两句：
ans += i-1-query(idx);
update(idx,1);
复杂度：
O(n log n)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int n,m;
int a[N],b[N],tr[N];
// cnt[i] 1-i 这些数出现的次数
int lowbit(int x){
return x&-x;
}
void update(int x,int k){
for(int i=x;i<=m;i+=lowbit(i))
tr[i] += k;
}
ll query(int x){
ll ans = 0;
for(int i=x;i>0;i-=lowbit(i)){
ans+=tr[i];
}
return ans;
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
b[i] = a[i];
}
sort(b+1,b+n+1);
m = 1;
for(int i=2;i<=n;i++){
if(b[i]!=b[m])b[++m]=b[i];
}
// 值域树状数组
long long ans = 0;
for(int i=1;i<=n;i++){
// a[i] 快速求出前面比我大数的数量
int idx = lower_bound(b+1,b+m+1,a[i]) - b;
ans += i - 1 - query(idx);
// 加进来 a[i]
update(idx,1);
}
cout<<ans;
return 0;
}
树状数组 + 差分：区间修改，单点查询
1. 差分数组
原数组：
a[1], a[2], a[3], ...
定义差分数组：
d[i] = a[i] - a[i-1]
那么原数组可以通过差分数组的前缀和还原：
a[x] = d[1] + d[2] + ... + d[x]
所以：
查询 a[x]，等价于查询差分数组 d 的前缀和。
2. 区间修改
如果要让：
[l,r] 全部增加 k
差分数组只需要修改两个位置：
d[l] += k;
d[r+1] -= k;
对应树状数组：
add(l,k);
add(r+1,-k);
例如：
原数组：
1 2 3 4 5
[2,4] 全部 +3
只需要：
d[2] += 3
d[5] -= 3
这样从位置 2 开始多出 3，到位置 5 再把这个影响取消。
3. 为什么树状数组存差分
初始化：
add(i,a[i]-a[i-1]);
说明树状数组维护的是：
d[i] = a[i]-a[i-1]
查询：
sum(x)
实际上求：
d[1]+d[2]+...+d[x]
根据差分：
= a[x]
所以：
cout << sum(x);
就是查询修改后的 a[x]。
4. 核心代码
区间增加：
add(x,k);
add(y+1,-k);
单点查询：
sum(x);
5. 一句话记忆
差分：
区间修改 → 修改两个点
树状数组：
快速维护差分数组的前缀和
最终：
区间修改 O(log n)
单点查询 O(log n)
树状数组维护差分 = 区间修改 + 单点查询。
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
typedef long long ll;
ll a[N],tr[N];
int lowbit(int x){
return x&-x;
}
void add(int x,int v){
for(int i=x;i<N;i+=lowbit(i))tr[i]+=v;
}
ll sum(int x){
ll ans = 0;
for(int i=x;i>0;i-=lowbit(i)){
ans+=tr[i];
}
return ans;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,a[i]-a[i-1]);
}
while(m-->0){
int op,x,y,k;
cin>>op;
if(op==1){
cin>>x>>y>>k;
add(x,k);
add(y+1,-k);
}
else{
cin>>x;
cout<<sum(x)<<endl;
}
}
return 0;
}
差分
树状数组
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
ll a[N],tr[N],n,m;
//找我的父亲结点是谁
int lowbit(int x){
return x&-x;
}
void update(int x,int k){
for(int i=x;i<N;i+=lowbit(i)){
tr[i] += k;
}
}
ll query(int x){
ll ans = 0;
for(int i=x;i>0;i-=lowbit(i)){
ans+=tr[i];
}
return ans;
}
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
update(i,a[i]);
}
while(m--){
int op,x,y;
cin>>op>>x>>y;
if(op==1){
update(x,y);
}else{
cout<<query(y)-query(x-1)<<"\n";
}
}
return 0;
}
树状数组：修改与查询思想
1. 树状数组解决什么问题
树状数组适合处理：
- 单点修改
- 前缀和查询
- 区间和查询
核心目标：
不一个一个修改、不一个一个累加，而是利用
lowbit快速跳到需要处理的结点。
2. lowbit 是什么
int lowbit(int x){
return x & -x;
}
lowbit(x) 表示：
x的二进制中，最低位的1所代表的值。
例如：
12 = 1100
lowbit(12) = 0100 = 4
树状数组中：
tr[x]
管理的区间长度就是：
lowbit(x)
所以 tr[x] 管理：
[x-lowbit(x)+1 , x]
例如：
tr[6] 管理 [5,6]
tr[8] 管理 [1,8]
3. 修改操作
代码：
void update(int x,int k){
for(int i=x;i<N;i+=lowbit(i)){
tr[i] += k;
}
}
修改的核心思想
如果：
a[x] 增加 k
那么所有管理区间中包含 x 的结点都必须增加 k。
例如修改：
a[3] += k
访问路径：
3 → 4 → 8
因为：
tr[3] 管 [3,3]
tr[4] 管 [1,4]
tr[8] 管 [1,8]
它们管理的区间都包含位置 3。
所以修改时不断：
i += lowbit(i);
可以理解成：
从当前结点不断跳到父亲结点。
修改记忆
修改：向上找父亲
x += lowbit(x)
时间复杂度：
O(log n)
4. 前缀和查询
代码：
ll query(int x){
ll ans = 0;
for(int i=x;i>0;i-=lowbit(i)){
ans += tr[i];
}
return ans;
}
query(x) 求的是：
a[1] + a[2] + ... + a[x]
也就是：
[1,x] 的和
查询的核心思想
不是从 1 加到 x，而是把：
[1,x]
拆成几个树状数组已经保存好的区间。
例如：
query(7)
访问：
7 → 6 → 4 → 0
对应：
tr[7] 管 [7,7]
tr[6] 管 [5,6]
tr[4] 管 [1,4]
所以：
[1,7]
= [1,4] + [5,6] + [7,7]
因此：
query(7)
= tr[7] + tr[6] + tr[4]
查询时不断：
i -= lowbit(i);
相当于：
每次拿走当前结点管理的一整块，再继续处理前面的部分。
查询记忆
查询：向前跳
x -= lowbit(x)
时间复杂度：
O(log n)
5. 区间和查询
因为：
query(r) = [1,r] 的和
query(l-1) = [1,l-1] 的和
所以：
[l,r]
=
[1,r] - [1,l-1]
代码：
query(r) - query(l-1)
6. 修改和查询对比
| 操作 | 跳法 | 思想 |
|---|---|---|
| 修改 | x += lowbit(x) |
找所有包含 x 的父结点 |
| 查询 | x -= lowbit(x) |
把前缀拆成几个完整区间 |
最重要的两句话：
修改：不断向上影响父结点。
查询：不断向前取完整区间。
乘法逆元入门
1. 什么是逆元？
如果：
a * x % p == 1
那么 x 就叫做 a 在模 p 意义下的逆元。
数学写法：
a × x ≡ 1 (mod p)
例如模 13：
2 × 7 = 14
14 % 13 = 1
所以：
2 的逆元是 7
可以把逆元理解为：
模运算世界里的倒数。
普通数学：
2 × 1/2 = 1
模 13：
2 × 7 % 13 = 1
2. 逆元有什么用？
主要用来做模意义下的除法。
普通数学：
a / b = a × 1/b
模运算：
a / b = a × inv(b)
代码：
a * inv[b] % p
例如：
7 / 2 mod 13
因为：
inv(2)=7
所以：
7 / 2
= 7 × 7
= 49
= 10 (mod 13)
验证：
2 × 10 = 20
20 % 13 = 7
因此模 13 意义下：
7 / 2 = 10
这里不是说普通数学中 7/2=10，而是说：
2 * 10 % 13 == 7
3. 逆元一定存在吗？
不一定。
例如模 6，找 2 的逆元：
2×1 % 6 = 2
2×2 % 6 = 4
2×3 % 6 = 0
永远得不到 1，所以 2 没有逆元。
一般：
gcd(a,p)=1
时 a 才有逆元。
如果 p 是质数，那么：
1 ~ p-1
全部都有逆元。
4. 快速幂求逆元
当 p 是质数时，根据费马小定理：
a^(p-1) ≡ 1 (mod p)
所以：
a^(-1) ≡ a^(p-2) (mod p)
因此：
inv = qpow(a,p-2,p);
ll qpow(ll a,ll b,ll p){
ll ans=1;
while(b){
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
记忆
a*x%p=1
→ x 是 a 的逆元
a/b mod p
→ a*inv[b]%p
一句话：
逆元就是模运算中的倒数，用来把除法变成乘法。
快速幂
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,p;
ll qpow(ll a,ll b,ll p){
ll ans = 1;
while(b){
if(b&1) ans = ans*a%p; //当前二进制位为1
a = a*a%p; //底数平方
b >>= 1; //b右移一位
}
return ans;
}
int main(){
cin >> a >> b >> p;
ll ans = qpow(a,b,p);
cout << a << "^" << b << " mod " << p << "=" << ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 300010;
int n,p;
int inv[N];
int qmi(int a,int k,int p){
int res=1;
while(k){
if(k&1) res=(LL)res*a%p;
a=(LL)a*a%p;
k>>=1;
}
return res;
}
int main(){
cin>>n>>p;
for(int i=1;i<=n;i++){
inv[i]=qmi(i,p-2,p);
}
for(int i=1;i<=n;i++){
cout<<inv[i]<<" ";
}
return 0;
}
C(n,k)
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6+10, mod = 1e9 + 7;
int fact[N], infact[N];
int qmi(int a, int k, int p){
int res = 1;
while (k){
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int main(){
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ ){
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
int n;
scanf("%d", &n);
while (n -- ){
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
}
return 0;
}
有帮助，赞一个