「SP5973」SELTEAM - Selecting Teams 解题报告

题面

即求：

$$\large \sum_{i=1}^kC_n^i\sum_{j=1}^iC_i^j\times j$$

有 $T(1\le T \le 10000)$ 组数据，其中 $1\le k \le n \le 100000$

解题思路

组合数+乱搞

分析

后面的 $\times j$ 显然不是很方便，因此提前枚举 $j$，也就是选哪个人为队长，得：

$$\large \sum_{i=1}^kC_n^i\times i\times 2^{i-1}$$

然而你并没有于是你就会发现这个模数 $8388608​$ 很奇怪，分解得：

$$\large 8388608=2^{23}$$

这不就很妙了嘛，这下 $i$ 就可以只枚举 $min(k,24)$ 了，至于 $C$，由于模数，不能直接求逆元，但是由于枚举的范围很小，因此可以直接用 $DP$ 预处理出来

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define p 8388608
#define N 100003
using namespace std;
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline int dec(rint x){return (x>=p)?x-p:x;}
int n,k,T,f[N][25],ans;LL res;
int main()
{
    rint i,j;T=read(),f[0][0]=1;//预处理
    for(i=1;i<=N;i++) {
        f[i][0]=1;
        for(j=1;j<=23;j++)
            f[i][j]=dec(f[i-1][j]+f[i-1][j-1]);
    }
    while(T--) {//枚举
        n=read(),k=min(read(),23),ans=0,res=1;
        for(i=1;i<=k;i++,res<<=1)
            ans=dec(ans+res*f[n][i]*i%p);
        printf("%d\n",ans);
    }
    return 0;
}