设 \(f(x,y,S) = 0/1\) 为当前巧克力长为 \(x\)，宽为 \(y\)，选出的 \(a_i\) 集合为 \(S\) 时，能否成功分割。

这样状态数有 \(xy \cdot 2^n\) 个，过多。

设集合 \(S\) 中元素的面积和为 \(sum_S\)。仔细观察不难发现：能够分割成功，当且仅当 \(sum_S = xy\)。

所以我们就可以只计算满足以上条件的状态。并且在满足以上条件的状态中，知道 \(x\) 和 \(y\) 其中一个就能直接计算出另一个。

所以设 \(f(x,S) = 0/1\) 为当前巧克力较短（较长也可以）边长为 \(x\)，选出的 \(a_i\) 集合为 \(S\) 时，能否成功分割。

 

先考虑特殊情况。

设全集为 \(U\)，集合 \(S\) 中面积的和为 \(sum_S\)。若 \(sum_U \neq xy\)，那么无解。

如果在有解的情况下，集合 \(S\) 中只有一个元素，那么一定有解。

  再考虑转移。

设 \(S_0 \subseteq S\)。

考虑到如果 \(S\) 有解，那么 \(S_0\) 一定有解，并且 \(S - S_0\) 也一定优解。

那么转移的方法就呼之欲出了。

枚举 \(S\) 的所有子集，设 \(x_0= \min{ \{ x,sum_{S_0}/x\} }\)，\(x_1 = \min{ \{ x,sum_{S_1}/x\} }\)。

这里进行一下数学分析……

已知 \(sum_S = sum_{S_0}+sum_{S_1}\)，\(sum_s = xy\)，显然 \(x \mid sum_S\)。

但 \(x\) 不一定都整除 \(sum_{s_0}\) 和 \(sum_{s_1}\)。举个例子：

\(x=2, y=5\)

\(xy = 5+5=10\)

\(x \nmid 5\)

这样就会转移到错误状态。

可以通过「切一刀后有一条边长不变」来理解。

所以为了达到正确的状态，求出 \(y= sum_S / x\)，\(y_0,y_1\) 同上。

\[ f(x,S) = \begin{cases} 1 & f(x_0/y_0,S_0) = f(x_1/y_1,S_1)=1 \\ 0 & \text{otherwise} \end{cases} \]

这里的斜杠是“或”的意思。

最终答案即为 \(f(\min{\{ x,y\}},U)\)，直接记忆化搜索就行了。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=16, M=105;
int _, n, x, y, U, a[N], sum[1<<N], f[M][1<<N];
inline int cnt(int x) {
    int a=0;
    while(x) a+=(x&1), x>>=1;
    return a;
}


inline bool dp(int x,int s) {
    if(f[x][s]!=-1) return f[x][s];
    // f[x][s]=-1 表示未计算
    int& dlt=f[x][s];
    if(cnt(s)==1) return dlt=1;
    // 特判只有一个元素的集合
    int y=sum[s]/x;
    for(int s0=(s-1)&s;s0;s0=(s0-1)&s) {
        int s1=s^s0;
        if(!(sum[s0]%x)&&dp(min(x,sum[s0]/x),s0)&&dp(min(x,sum[s1]/x),s1)) return dlt=1;
        if(!(sum[s0]%y)&&dp(min(y,sum[s0]/y),s0)&&dp(min(y,sum[s1]/y),s1)) return dlt=1;
        // 被x或y整除才去计算这个状态
    }
    return dlt=0;
}


inline void sol() {
    memset(f,-1,sizeof(f)), memset(sum,0,sizeof(sum));
    U=(1<<n)-1;
    scanf("%d%d",&x,&y);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int s=0;s<=U;++s) for(int i=0;i<n;++i) if(s&(1<<i)) sum[s]+=a[i+1];
    // 预处理所有集合的sum
    bool fg;
    if(sum[U]!=x*y) fg=0; else fg=dp(min(x,y),U);
    // 特判
    printf("Case %d: %s\n",++_,fg? "Yes":"No");
}


int main() { for(;scanf("%d",&n)&&n;sol()); }