树与图上的计数专题
很明显可以用小根堆来处理 但是数据范围不允许
考虑线性想法 这个做法很好很实用
针对每次维护最小的且每次最多增加一个最小 都可以用这样的方法 ！！！！完全可以替代小根堆
最后pufer转化为树反过来就好了 思路是一样的
#include
using namespace std;
#define lowbit(x) x&(-x)
#define int ll
#define ll long long
const int maxn=5e6+5;
int cnt;
int a[maxn],ans[maxn],in[maxn];
int n,c;
signed main(){
cin>>n>>c;
if(c==1){
for(int i=1;i<=n-1;i++)cin>>a[i],in[a[i]]++;
int minn;
for(int i=1;i<=n-1;i++)
if(!in[i]){
minn=i;break;
}
int now=minn;
while(cnt>a[i],in[a[i]]++;
a[n-1]=n;in[n]++;
int minn;
for(int i=1;i<=n-1;i++)
if(!in[i]){
minn=i;break;
}
int now=minn;
for(int i=1;i<=n-1;i++){
ans[now]=a[i];
in[a[i]]--;
if(!in[a[i]]&&a[i] 
https://www.luogu.com.cn/problem/P2290 就是一道经典的板子题
题目要求完全二分图个数 考虑从完全图来推 完全图pufer会剩下两个点 到完全二分图这里这两个点一定是分居一边
一边的一个点一定有出边连向另一边 如果一一对应的话就是分别有n-1个和m-1个
选n-1次有m个选择方案 选m-1个有n个选择方案 所以答案就是ksm（n-1,m）× ksm(m-1,n)
注意long long 相乘可能会爆 所以要用到快速乘
点击查看代码
#include
typedef long long ll;
typedef long double ld;
ll n,m,p;
ll mul(ll a,ll b){
ll res=0;
while(b){
if(b&1)res=(res+a)%p;
b>>=1;a=a*2%p;
}
return res;
}
ll ksm(ll a,ll b)
{
ll ret=1;
for(;b;b>>=1,a=mul(a,a))
if(b&1) ret=mul(ret,a);
return ret;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&p);
printf("%lld\n",mul(ksm(n,m-1),ksm(m,n-1)));
}
点击查看代码
#include
#define ll long long
#define ull unsigned long long
#define met(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define bep(i, a, b) for(int i = a; i >= b; i--)
#define re return 0
using namespace std;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const ll INF = 2e18+1;
const int inf = 1e9 + 15;
const double eps = 1e-7;
const int maxn = 1e6 + 5;
ll d[3003][3003], p[3003][3003];
string ma[3003];
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
n--, m--;
rep(i, 0, n) cin >> ma[i];
d[0][0] = p[0][0] = 1;
rep(i, 0, n){
rep(j, 1, m){
if(ma[i][j] == '.'){
if(i) d[i][j] += d[i-1][j];
if(j) d[i][j] += d[i][j-1];
d[i][j] %= mod;
}
}
}
rep(i, 1, n){
rep(j, 0, m){
if(ma[i][j] == '.'){
if(i) p[i][j] += p[i-1][j];
if(j) p[i][j] += p[i][j-1];
p[i][j] %= mod;
}
}
}
cout << ((d[n-1][m]*p[n][m-1])%mod - (d[n][m-1]*p[n-1][m])%mod + mod) % mod << endl;
re;
}
这个题目平移一条直线让我想到了卡特兰数
跨过y=x的线就相当于到了y=x+1的线 再对称一下就是(-1,1)到(n,n)
下面的链接讲得很详细
叶子期望=(各个情况叶子总和)/各个情况
难点就在于怎么算出各个情况下叶子总数
对于每棵n个点的二叉树，如果里面有k个叶节点，那么我们分别把这k个叶子删去会得到k棵n?1个点的二叉树；
而每棵n?1个点的二叉树恰好有n个位置可以悬挂一个新的叶子，所以每棵n?1个点的二叉树被得到了n次；
这个是实验出来的 我也不知道怎么推 不过确实神奇
综上，我们即可得出结论：所有n个点的二叉树的叶子个数和等于n-1个点的二叉树个数×n。
这个题是卡特兰数另一个金典的公式的几何形态
一个点的度数为d 在prufer序列中出现的次数是d-1 每个点度数的价值可以预处理出来
总容量n-2 但是有n个点的价值是要计算的 因为有些点的度数是1 容量为0 不会出现在prufer序列当中 但是该价值任然要计算的
一般的背包是没法处理的 可以多开一维 但是复杂度不允许 考虑对每个点的价值都-f(1) 最后减了多少个f(1)就是选了多少个度数不为1的点
最后加上n个度数为1的点的价值 就是最终的答案 很巧妙！！！！