A：非常裸的dp。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define P 1000000007 #define N 32 int a,b,c,d,f[N][N][N][N][4]; 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[1][0][0][0][0]=f[0][1][0][0][1]=f[0][0][1][0][2]=f[0][0][0][1][3]=1; for (int i=1;i<a+b+c+d;i++) for (int x=0;x<=a;x++) for (int y=0;y<=b;y++) for (int z=0;z<=c;z++) { int t=i-x-y-z; if (t>d) continue; for (int p=0;p<4;p++) for (int q=0;q<4;q++) if (p!=q) { if (q==0&&x<a) inc(f[x+1][y][z][t][q],f[x][y][z][t][p]); if (q==1&&y<b) inc(f[x][y+1][z][t][q],f[x][y][z][t][p]); if (q==2&&z<c) inc(f[x][y][z+1][t][q],f[x][y][z][t][p]); if (q==3&&t<d) inc(f[x][y][z][t+1][q],f[x][y][z][t][p]); } } cout<<((f[a][b][c][d][0]+f[a][b][c][d][1])%P+(f[a][b][c][d][2]+f[a][b][c][d][3])%P)%P; return 0; }
B：非常裸的组合。我又学傻了第一眼居然容斥还好拍了。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 200010 #define P 1000000007 int n,m,k,ans=0,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[0]=1;for (int i=1;i<=n+m;i++) fac[i]=1ll*fac[i-1]*i%P; inv[0]=inv[1]=1;for (int i=2;i<=n+m;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P; for (int i=1;i<=n+m;i++) inv[i]=1ll*inv[i]*inv[i-1]%P; if (m-k&1) {cout<<0;return 0;} cout<<1ll*C(n,k)*C((m-k>>1)+n-1,n-1)%P; return 0; }
C：非常裸的meet in the middle。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 300010 #define ll long long int n,b[40]; ll a[2][N],l,r,ans,m; void dfs(int k,int n,int p,ll s) { if (k>n) a[p][++a[p][0]]=s; else { dfs(k+1,n,p,s); dfs(k+1,n,p,s+b[k]); } } ll calc(ll k) { ll s=0;int x=a[1][0]; for (int i=1;i<=a[0][0];i++) { while (x&&a[1][x]+a[0][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=1;i<=n;i++) r+=(b[i]=read()); dfs(1,n>>1,0,0); dfs((n>>1)+1,n,1,0); sort(a[0]+1,a[0]+a[0][0]+1); sort(a[1]+1,a[1]+a[1][0]+1); while (l<=r) { ll mid=l+r>>1; if (calc(mid)>=m) ans=mid,r=mid-1; else l=mid+1; } cout<<ans; return 0; }
result：300 rank1