题目链接
HDU4945
题解
题意
给出若干个数字，从其中挑出两个相同的数字则可进行合并，合并后产生值为二者之和的新数字且原有两数字消失。
求能够凑出2048的集合的数量。
思路
动态规划。
我们规定:
有效数字为有能力对凑出2048有贡献的数字。
要凑出2048，则有效数字只能从
2
i
2^i
2i 中进行选择。
设
u
s
e
[
i
]
[
j
]
=
从
2
i
中
挑
选
j
个
的
方
法
的
数
量
use[i][j] = 从2^i中挑选j个的方法的数量
use[i][j]=从2i中挑选j个的方法的数量，
d
p
[
i
]
[
j
]
=
凑
出
数
字
k
属
于
区
间
[
j
∗
2
i
,
(
j
+
1
)
∗
2
i
)
的
方
法
的
数
量
dp[i][j] = 凑出数字 k 属于区间 [j * 2^i, (j + 1) * 2^i) 的方法的数量
dp[i][j]=凑出数字k属于区间[j∗2i,(j+1)∗2i)的方法的数量
则状态转移方程为
d
p
[
i
]
[
j
]
=
(
d
p
[
i
−
1
]
[
k
]
+
d
p
[
i
−
1
]
[
k
+
1
]
)
∗
u
s
e
[
i
]
[
j
−
k
/
2
]
dp[i][j] = (dp[i - 1][k] + dp[i - 1][k + 1]) * use[i][j - k / 2]
dp[i][j]=(dp[i−1][k]+dp[i−1][k+1])∗use[i][j−k/2]
其中
k
∈
[
0
,
2
∗
j
]
且
k
为
偶
数
k \in[0,2 * j] 且 k 为偶数
k∈[0,2∗j]且k为偶数。
方程可以根据方程定义推导出来。
AC代码
#include <bits/stdc++.h>
using namespace std
;
using ll
= long long;
#define mms(a, x) memset(a, x, sizeof(a))
int const N
= 1e5 + 10;
ll
const Mod
= 998244353;
ll fac
[N
], inv
[N
];
int a
[N
], nums
[30];
ll dp
[15][N
], use
[15][N
];
int n
;
int two(int n
) {
if (n
== 0) return 20;
int ans
= 0;
while (n
!= 1) {
if (n
& 1) return 20;
n
>>= 1;
ans
+= 1;
}
return ans
;
}
ll
FastPower(ll a
, ll b
) {
ll ans
= 1;
while (b
) {
if (b
& 1) ans
= ans
* a
% Mod
;
a
= a
* a
% Mod
;
b
>>= 1;
}
return ans
% Mod
;
}
void fact(int n
) {
fac
[0] = 1LL;
for (ll i
= 1; i
<= n
; i
++) {
fac
[i
] = (fac
[i
- 1] * i
) % Mod
;
}
}
void init() {
mms(a
, 0);
mms(dp
, 0);
mms(nums
, 0);
mms(use
, 0);
}
ll
C(int n
, int m
) {
if (m
> n
) return 0;
return (fac
[n
] * (FastPower(fac
[m
], Mod
- 2) % Mod
* FastPower(fac
[n
- m
], Mod
- 2) % Mod
) % Mod
) % Mod
;
}
void getUse() {
for (int i
= 0; i
<= 10; i
++) {
for (int j
= 0; j
< 2048; j
++) {
use
[i
][j
] = C(nums
[i
], j
);
}
}
}
ll
solve() {
getUse();
for (int j
= 0; j
< 2048; j
++) {
dp
[0][j
] = use
[0][j
];
}
for (int i
= 1; i
<= 10; i
++) {
int cnt
= (1 << (11 - i
));
for (int j
= 0; j
< cnt
; j
++) {
for (int k
= 0; k
<= 2 * j
+ 1; k
+= 2) {
if (!use
[i
][j
- k
/ 2] || !(dp
[i
- 1][k
] + dp
[i
- 1][k
+ 1])) continue;
dp
[i
][j
] += (dp
[i
- 1][k
] + dp
[i
- 1][k
+ 1]) * use
[i
][j
- k
/ 2] % Mod
;
}
dp
[i
][j
] %= Mod
;
}
}
ll cannot
= FastPower(2, nums
[20]);
ll notSat
= (dp
[10][0] + dp
[10][1]) % Mod
;
ll ans
= (FastPower(2, n
- nums
[20]) - notSat
+ Mod
) % Mod
* cannot
% Mod
;
return ans
;
}
int main() {
fact(N
);
int cnt
= 1;
while (scanf("%d", &n
) && n
) {
init();
for (int i
= 1; i
<= n
; i
++) {
scanf("%d", &a
[i
]);
nums
[two(a
[i
])] += 1;
}
printf("Case #%d: %lld\n", cnt
, solve());
cnt
+= 1;
}
return 0;
}
