题目描述

在 $x=\square 1\square 2\square 3\square 4\square 5\square 6\square 7\square 8\square 9$ 的 $\square$ 内填入 $+$ 或 $-$.
(1) 求证：$27$ 可以被这样表示，$28$ 不可以.
(2) 求 $x=7$ 时的方案数。

题解

(1) 求证：$27$ 可以被这样表示，$28$ 不可以.

证明：$27=1+2+3+4+5+6+7+8-9$，可以被表示

设填入 $-$ 后的数字的总和为 $S$，

则 $x=((1+2+...+9)-S)-S=45-2S$

$\because S$ 为整数

$\therefore 2S$ 为偶数

$\therefore 45-2S$ 为奇数，即 $x$ 为奇数

$\because 28$ 为偶数

$\therefore 28$ 不可以被表示

​ (2) 求 $x=7$ 时的方案数。
这题我们可以用一个比较 $\text{OI}$ 的方法——$\text{DP}$（动态规划）。

​ 定义 $f_{i,j}$ 表示已经填了 $i$ 个方格，答案为 $j$ 的情况下的方案数。

​ 很显然，$f_{0,0}=1$.

​ 递推式也非常简单：$f_{i,j}=f_{i-1,j-i}+f_{i-1,j+i}$.

​ 然后就手推到 $f_{9,7}$ 就可以了，
表格如下（空格子表示值为 $0$）：

即：方案数为 $f_{9,7}=21$.

---

计算量比较大，这里我直接用代码写了，由于下标为负数可能会出错，所以把下标统一加上 $200$：

#include<bits/stdc++.h>
using namespace std;
int f[405][405];
int main(){int n=9;f[0][200]=1;for(int i=1;i<=n;i++){for(int j=-55;j<=55;j++){f[i][j+200]=f[i-1][j+200-i]+f[i-1][j+200+i];}}cout<<f[n][200+7]<<endl;return 0;
}

​ 最终算出答案为 $21$。

​ 虽然这也比较麻烦，但比枚举快多了。

​