Contest 3

　　A：非常裸的dp。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define P 1000000007

#define N 32

int a,b,c,d,f[N][N][N][N][];

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int main()

{

    freopen("count.in","r",stdin);

    freopen("count.out","w",stdout);

    a=read(),b=read(),c=read(),d=read();

    f[][][][][]=f[][][][][]=f[][][][][]=f[][][][][]=;

    for (int i=;i<a+b+c+d;i++)

        for (int x=;x<=a;x++)

            for (int y=;y<=b;y++)

                for (int z=;z<=c;z++)

                {

                    int t=i-x-y-z;

                    if (t>d) continue;

                    for (int p=;p<;p++)

                        for (int q=;q<;q++)

                        if (p!=q)

                        {

                            if (q==&&x<a) inc(f[x+][y][z][t][q],f[x][y][z][t][p]);

                            if (q==&&y<b) inc(f[x][y+][z][t][q],f[x][y][z][t][p]);

                            if (q==&&z<c) inc(f[x][y][z+][t][q],f[x][y][z][t][p]);

                            if (q==&&t<d) inc(f[x][y][z][t+][q],f[x][y][z][t][p]);

                        }

                }

    cout<<((f[a][b][c][d][]+f[a][b][c][d][])%P+(f[a][b][c][d][]+f[a][b][c][d][])%P)%P;

    return ;

}

　　B：非常裸的组合。我又学傻了第一眼居然容斥还好拍了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 200010

#define P 1000000007

int n,m,k,ans=,fac[N],inv[N];

int C(int n,int m){return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;}

int main()

{

    freopen("array.in","r",stdin);

    freopen("array.out","w",stdout);

    n=read(),m=read(),k=read();

    fac[]=;for (int i=;i<=n+m;i++) fac[i]=1ll*fac[i-]*i%P;

    inv[]=inv[]=;for (int i=;i<=n+m;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;

    for (int i=;i<=n+m;i++) inv[i]=1ll*inv[i]*inv[i-]%P;

    if (m-k&) {cout<<;return ;}

    cout<<1ll*C(n,k)*C((m-k>>)+n-,n-)%P;

    return ;

}

　　C：非常裸的meet in the middle。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 300010

#define ll long long

int n,b[];

ll a[][N],l,r,ans,m;

void dfs(int k,int n,int p,ll s)

{

    if (k>n) a[p][++a[p][]]=s;

    else

    {

        dfs(k+,n,p,s);

        dfs(k+,n,p,s+b[k]);

    }

}

ll calc(ll k)

{

    ll s=;int x=a[][];

    for (int i=;i<=a[][];i++)

    {

        while (x&&a[][x]+a[][i]>k) x--;

        s+=x;

    }

    return s;

}

int main()

{

    freopen("subset.in","r",stdin);

    freopen("subset.out","w",stdout);

    n=read();cin>>m;

    for (int i=;i<=n;i++) r+=(b[i]=read());

    dfs(,n>>,,);

    dfs((n>>)+,n,,);

    sort(a[]+,a[]+a[][]+);

    sort(a[]+,a[]+a[][]+);

    while (l<=r)

    {

        ll mid=l+r>>;

        if (calc(mid)>=m) ans=mid,r=mid-;

        else l=mid+;

    }

    cout<<ans;

    return ;

}

　　result：300 rank1