Steven_MengのBlog

传送门

考虑先选$p$名队员,方法数为$C^p_n$,其中$1\le p\le k$,然后从$p$名队员中钦定一名队长,方法数为$p$,其他的队员可选可不选,有$2^{p-1}$种方法。
所以总的方案数为

但是这似乎也没什么用,算这个式子的复杂度为$O(k)$,有$T$组数据,总复杂度为$O(Tk)$。
经过一(cha)番(zhao)思(ti)考(jie)后发现模数$8388608=2^{23}$,所以对于$p \ge 24$,$C^p_n \times p \times 2^{p-1}=0$,可以不用考虑。
所以单次查询时间复杂度为$O(min(k,23))$,总复杂度为$O(min(k,23) \times T)$,可以过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define MOD 8388608
#define MAXN 1000005
#define MAXK 30
#define ll long long
using namespace std;
ll C[MAXN][MAXK],pow2[MAXK];
inline void Init(){
for (register int i=0;i<MAXN;++i){
C[i][0]=1;
for (register int j=1;j<=min(23,i);++j){
C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
}
}
pow2[0]=1;
for (register int i=1;i<MAXK;++i){
pow2[i]=pow2[i-1]<<1ll;
}
}
int main(){
Init();
int T;
scanf("%d",&T);
while (T--){
ll n,k;
scanf("%lld%lld",&n,&k);
ll ans=0;
for (register int i=1;i<=min(k,23ll);++i){
ans=(ans+pow2[i-1]*(ll)i*C[n][i])%MOD;
}
printf("%lld\n",ans);
}
}

p.s.这种在模数上下坑的题目我还是第一次见到

 评论