传送门:CF
[前题提要]:近期在集中刷1900+的题,原本感觉这类题的思维难度对自己来说似乎没什么大问题,拿到手之后就开始乱贪心,然后就Wa4了,狠狠地被这道题给教育了,故记录一下
看了题解之后感觉这种做法之前在某道题中碰到过类似的,但是想不起来了…
我个人认为这道题的关键点在于得出下面这个结论:对于本题来说,我们将原题简化为固定左边的选手胜利,然后可以随意排列选手的位置.个人感觉有了这个结论之后,后面的组合数问题简直不要太简单(可以说根本没有解释的必要),但是可惜的是,几乎所有题解都直接我们不妨假设每次比赛均选择靠左侧的选手赢.根本没有人解释这一点.
下面简单来说明一下上述结论为什么是对的.考虑随便选取一棵树,类似于下图(红线代表胜利,黑线表示失败):
假设上述序列是一种最优方案,此时满足不是所有红线都在左边.但是因为我们的序列是可以随便排列的,我们完全可以将红线在右边的子树和左边的子树进行一个调换,此时就将一个在右边的红线换到了左边,并且上述操作是不会影响
k
k
k次换边的,因为假设原本
<
u
,
v
1
>
<u,v_1>
<u,v1>是红线,我们想将其换成
<
u
,
v
2
>
<u,v_2>
<u,v2>,此时我们调换了
v
1
,
v
2
v_1,v_2
v1,v2,此时的
v
1
,
v
2
v_1,v_2
v1,v2依旧存在,此时我们依旧可以将红线改为
<
u
,
v
2
>
<u,v_2>
<u,v2>.类似的,对于任意一颗不是所有红线都在左边的决策树,我们可以采取以下策略将其改为一颗红线都在左边的决策树:对于任意一条红线在右边的
<
u
,
v
>
<u,v>
<u,v>,我们可以将
v
v
v整颗子树和左子树进行交换,然后递归解决
v
v
v子树的红线分布问题.
在上述简化的前提下.我们会发现对于给定的 k k k,最终胜利的位置是可以确定的.逆转一下,也就是说对于任意的位置,我们都可以求出该位置成为最终胜利者需要的最小的k.举例来说,对于上述的 a 1 a_1 a1,我们会发现其需要的 k k k为0, a 2 a_2 a2需要1, a 3 a_3 a3需要1, a 4 a_4 a4需要2.(此时的 a 3 a_3 a3是原本的 a 4 a_4 a4).设 w [ k ] w[k] w[k]最少需要 k k k次改变才能成为胜利者的人数.我们会发现此时是 1 , 2 , 1 1,2,1 1,2,1.贪心的想,显然我们需要将编号小的选手放在需要的 k k k小的节点上,因为我们要尽量让编号小的选手胜利.
那么我们现在的问题就变成了怎么解决每个叶子节点需要的
k
k
k.其实不难发现,对于每个节点来说,他们的状态都是可以通过上一层的节点的状态递推过来的.如果一个节点,它相对于父亲节点位于左儿子的位置,那么它所需要的k和父节点相同,否则它需要的k是父节点+1.也就说每一个节点都会引出一个和本身权值相同的点以及一个权值+1的点,这个现象其实就是杨辉三角.当然通过手模多画几层也不难发现分布是杨辉三角.
那么我们现在的答案显然就是杨辉三角第 n n n层的前 k k k个数字之和.求一下组合数即可.
下面是具体的代码部分;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
inline void print(__int128 x){
if(x<0) {putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const int mod=1e9+7;
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int qpow(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
int fac[maxn],in_fac[maxn];
void init(int limit=2e5) {
fac[0]=1;
for(int i=1;i<=limit;i++) {
fac[i]=fac[i-1]*i%mod;
}
in_fac[limit]=qpow(fac[limit],mod-2);
for(int i=limit-1;i>=0;i--) {
in_fac[i]=in_fac[i+1]*(i+1)%mod;
}
}
int C(int a,int b) {
return fac[a]*in_fac[b]%mod*in_fac[a-b]%mod;
}
signed main() {
init();
int n=read();int k=read();
if(k>=n) {
cout<<qpow(2,n)<<endl;
return 0;
}
int ans=0;
for(int i=0;i<=k;i++) {
ans+=C(n,i);ans%=mod;
}
cout<<ans<<endl;
return 0;
}
