SP5973 SELTEAM - Selecting Teams

【题目描述】

他已经有 n 个心仪的妹子了，但随着时间的流逝，只有 m（1<=m<=k）个直伴随在他的身边，而小小迪发现他只爱上了这其中的 l（1<=l<=m）个妹子从这 l 个中选出一个妹子作为他的真爱，向她告白。但小小迪并不知道未来会发生什么，他可以得知的只有 n 和 k。你作为小小迪的专属膜法师，决定帮助他算出未来会有多少种不同的爱情故指 m 个妹子不同或 l 个妹子不同或真爱不同，m，l 见上文）小小迪会历经 T 世情劫，所以你要帮他算 T 次。答案对 8388608取模。（2^23）【输入格式】第一行一个数 T。接下来 T 行每行两个数表示 n 和 k。

【输出格式】

输出 T 行每行一个整数表示答案。

【样例输入 1】

2 2

7 1

5 3

【样例输出 1】

165

【数据包规模】

对于 40%的数据 1<=k<=n,T<=200；

对于另 20%的数据 T=1；

对于 100%的数据 1<=T<=10000,1<=k<=n<=10000

sol：如果看完题毫无思路是正确的，在你没有发现Mod=8388608=2²³前这就是到不可做题。

因为是2²³，容易知道（XJB乱猜）m只要枚举到23就可以了（我怕溢出枚举到25），事实证明果然是这样（对拍拍上了）

Ps：代码真的很短，但是仍然非常丑丑丑丑丑

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

inline ll read()

{

    ll s=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+'');    return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const ll Mod=;

int T,n,Up;

ll C[][];

int main()

{

    int i,j;

    C[][]=;

    for(i=;i<=;i++)

    {

        C[i][]=;

        for(j=;j<=;j++)

        {

            C[i][j]=(C[i-][j-]+C[i-][j])%Mod;

        }

    }

    R(T);

    while(T--)

    {

        ll ans=;

        R(n); R(Up);

        for(i=;i<=min(,Up);i++)

        {

            for(j=;j<=i;j++)

            {

                ans+=C[n][i]*C[i][j]%Mod*j%Mod;

                ans-=(ans>=Mod)?Mod:;

            }

        }

        Wl(ans);

    }

    return ;

}

/*

input

3

2 2

7 1

5 3

output

6

7

165

*/