惑疑的凯小

DP

---

题面

现有$n$个砝码,重量分别为$a_1,a_2,a_3,...,a_n$。$xzy$太好吃了,于是吃掉了其中$m$个砝码。
现在$xzy$想知道,他在剩余的砝码中随机选取一些砝码(不能不选),正好称出$k$的重量的方案数?
但他要我们输出的是答案 除以 $xzy$吃掉砝码的方案数，并对$6249433$取模。

• $30pts$ $n\leq233,m=0$
• $100pts$ $n\leq20,m<n,a_i\leq100$

解析

$30pts$算法

显然可以设$dp[i][sum]$表示前$i$个数中随便取数后和为$sum$的方案数。
则枚举$i$和$sum(sum\in[1,k])$，可得转移方程
$dp[i][sum+a[i]]+=dp[i-1][sum]$
$dp[i][sum]+=dp[i-1][sum]$
复杂度最坏为$O(nk)$

考场龟速$100pts$算法

$O(2^n)$枚举去掉哪些砝码。
然后使用$30pts$算法即可。
使用快速幂和费马小定理(要求$q$为质数）

$$\frac{1}{p}=p^{mod-2}(\mod q)$$
就可以处理答案了。
复杂度$O(2^nnk)$，理论会炸，但$0.64s$过了？？？

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll unsigned long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=250,mod=6249433;
int n,m,k,a[N],dp[N][N*100],pr[N],vis[N];
ll ans;
il ll gi() 
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re ll x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
il ll check(re ll x)
{
  while(x>=mod) x-=mod;
  return x;
}
il ll ksm(re ll x,re ll n)
{
  re ll S=1,T=x;
  while(n)
    {
      if(n&1) S=check(S*T);
      T=check(T*T);
      n>>=1;
    }
  return S;
}
il void solve()
{
  //fp(i,1,n) printf("%d ",pr[i]);puts("");
  fp(i,1,k) fp(j,0,n) dp[j][i]=0;
  fp(i,1,n) dp[i][a[i]]=1;
  fp(i,1,k)
    fp(j,1,n)
    if(!vis[j])
      {
    dp[j][i+a[j]]=check(dp[j][i+a[j]]+dp[pr[j]][i]);
    dp[j][i]=check(dp[j][i]+dp[pr[j]][i]);
      }
  re int ysn=n;while(vis[ysn]&&ysn) --ysn;
  ans=check(ans+dp[ysn][k]);
}
il void dfs(re int x,re int tot)
{
  if(tot<0) return;
  if(x==n+1) {if(!tot) solve();return;}
  fp(i,0,1)
    if(i) vis[x]=1,pr[x+1]=pr[x],dfs(x+1,tot-1),vis[x]=0,pr[x+1]=x;
    else
      {
    if(a[x]>k) pr[x+1]=pr[x];
    dfs(x+1,tot);
      }
}
il ll jc(re ll s,re ll e,re int flag)
{
  re ll pzy=1;
  fp(i,s,e) pzy=check(pzy*i);
  if(flag) pzy=ksm(pzy,mod-2);
  return pzy;
}
int main()
{
  freopen("htam.in","r",stdin);
  freopen("htam.out","w",stdout);
  re int T=gi();
  while(T--)
    {
      n=gi()^ans,m=gi()^ans,k=gi()^ans;ans=0;
      if(k==0) {puts("0");continue;}
      fp(i,1,n) a[i]=gi(),pr[i]=i-1;
      dfs(1,m);
      re ll eat=1;
      if(m) eat=check(jc(1,n-m,0)*jc(m+1,n,1));
      //printf("%llu %llu\n",eat,ans);
      ans=check(ans*eat);
      wri(ans);putchar('\n');
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}

考场感想：

• 编译时不开$O2$导致自己一直以为过不了(开了从$1.1s->0.7s$)
• 用$unsigned\ long\ long$乘炸了都看不出来（所以一开始别用）
• 龟速模是卡常利器

贼快$AC$算法

$O(2^n)$枚举每个数取不取，如果取了$p$个数，取了的数和为$k$，就会生成$C_{n-p}^m$个合法方案（剩下$n-p$个数有$m$个被吃了）。
复杂度$O(2^n)$，$0.05s$叹为观止。（其实我考场上也想到过。。。）