前置芝士

二项式定理，组合数

正文

• 二项式定理

\[(x+y)^n=\sum_{i=0}^{n} \binom{n}{i}x^{n}y^{n-i}\]

带入\(x=y=1\)，得

\[2^n=\sum_{i=0}^{n}\binom{n}{i}\]

---

• 转化

首先转化，考虑枚举人数，然后先取队长，剩下任意
取。

答案即为

\[\sum_{i=1}^{k}i\binom{n}{i} \sum_{j=0}^{i-1}\binom{i}{j}\]

后面的式子根据刚刚得出的结论，可以替换为\(2^{i-1}\)

所以

\[\texttt{ans} = \sum_{i=1}^{k}i\binom{n}{i}2^{i-1}\]

然后可以发现模数是\(2^{23}\)，所以枚举人数只要到23即可。

\(Code\)

#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long 
using namespace std;
inline int read(){
    register int x=0,f=0,ch=getchar();
    while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
    return f?-x:x;
}
#define P 8388608
const int MAX=100005; 
int C[MAX][30];
inline void Gcom(){
    for(register int i=0;i<=MAX;++i){
        C[i][0]=1;
        for(register int j=1;j<=23&&j<=i;++j){
            C[i][j]=C[i-1][j]+C[i-1][j-1];
            C[i][j]%=P;
        }
    }
} 
int n,k,t,ans;
signed main(){
    Gcom();
    t=read();
    while(t--){
        ans=0;
        n=read(),k=read();
        for(register int i=1;i<=k&&i<=23;++i){
            ans+=C[n][i]*i%P*(1<<i-1)%P;
            ans%=P;
        }
        printf("%lld\n",ans%P);     
    }

    return 0;
}