Codeforces Round #742 (Div. 2) - Carrying Conundrum

前言

一道可以简单也可以复杂的题目…

题解

题意是说,把竖式加法的进位从往高位进一位改为进两位,求对于给定的运算结果$n$,有多少种可能的$a,b$在竖式上相加能够得到。

image-20210911170514295

性质

由于更改了进位方式,使得奇数位的加法只会影响奇数位的结果,偶数位同理。

因此,我们完全可以把奇数位和偶数位独立开来,分成两个部分去讨论。

如$1234567$,可分为$a=1357$和$b=246$单独考虑。

由于单独考虑后,进位方法与普通加法相同。若考虑$0+a / 0+b$这样的方案在内,方案数一共有$a+1$种和$b+1$种,又因为奇数位和偶数位相互独立,总方案数为$(a+1)*(b+1)$​。

但题目要求了相加的数字必需是正整数,因此$0+a/0+b$这样的方案是不合法的,我们在原基础上减去$2$就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

clock_t START_TIME, END_TIME;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
std::cout << head << ", ";
Print(rail...);
}

int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int t, n;
signed main(void)
{
t = read();
//START_TIME = clock();
while(t--)
{
n = read();
vector<int> v1, v2;
int flag = 0, res1 = 0, res2 = 0;
while(n)
{
flag ^= 1;
flag ? v1.push_back(n % 10) : v2.push_back(n % 10);
n /= 10;
}
reverse(v1.begin(), v1.end());
reverse(v2.begin(), v2.end());
for(auto x : v1) res1 = (res1 * 10) + x;
for(auto x : v2) res2 = (res2 * 10) + x;
printf("%lld\n", (res1 + 1) * (res2 + 1) - 2);
}
//END_TIME = clock();
//printf("%.5lf ms\n", (double)(END_TIME - START_TIME) / CLOCKS_PER_SEC * 1000);
return 0;
}

二进制枚举

我们设数字$n$的长度为$len$​,那么就可以设一个长度为$len$的$01$串,代表数字$n$的第$i$位是否有被进位影响。

比赛时候就是这么写的然后写挂了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

clock_t START_TIME, END_TIME;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
std::cout << head << ", ";
Print(rail...);
}

int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int t, cnt[maxn];

void inits(){
for(int i = 0; i < 10; i++)
for(int j = 0; j < 10; j++)
cnt[i + j]++;
}
int solve(){
string str;
cin >> str;
int len = str.length(), ans = 0;
//reverse(str.begin(), str.end());
for(int sta = 0; sta < (1 << len); sta++)
{
int res = 1;
if(sta & 3) continue;
for(int i = 0; i < len; i++)
{
int num = str[i] - '0';
//当前数字是有进位的,像5->15,3->13这样子
if(sta & (1 << i)) num += 10;
//后两位也有进位,为了计算当前位的方案数,要撤销掉后两位进位的贡献
if(i + 2 < len && ((1 << i + 2) & sta)) num--;
if(num < 0) num = 20;
res *= cnt[num];
}
ans += res;
}
return ans;
}
signed main(void)
{
inits();
t = read();
//START_TIME = clock();
while(t--)
printf("%lld\n", solve() - 2);
//END_TIME = clock();
//printf("%.5lf ms\n", (double)(END_TIME - START_TIME) / CLOCKS_PER_SEC * 1000);
return 0;
}

记忆化搜索

设$dp[i][cur][nxt]$为第$i$位,当前是否有进位$cur=0/1$,前一位是否有进位$nxt=0/1$​,以此记忆化搜索即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

clock_t START_TIME, END_TIME;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
std::cout << head << ", ";
Print(rail...);
}

int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int t, n;
int cnt, num[maxn], dp[maxn][2][2];
int dfs(int pos, int cur, int nxt){
if(pos < 1)
return (cur || nxt) ? 0 : 1;
if(~dp[pos][cur][nxt]) return dp[pos][cur][nxt];
int res = 0;
for(inti = 0; i < 10; i++)
for(int j = 0; j < 10; j++)
{
int now = i + j + cur;
if(now % 10 != num[pos]) continue;
res += dfs(pos - 1, nxt, now / 10);
}
return dp[pos][cur][nxt] = res;
}
signed main(void)
{
t = read();
//START_TIME = clock();
while(t--)
{
cnt = 0;
n = read();
while(n) num[++cnt] = n % 10, n /= 10;
reverse(num + 1, num + cnt + 1);
memset(dp, -1, sizeof(dp));
printf("%lld\n", dfs(cnt, 0, 0) - 2);
}
//END_TIME = clock();
//printf("%.5lf ms\n", (double)(END_TIME - START_TIME) / CLOCKS_PER_SEC * 1000);
return 0;
}
如果你觉得还不错,就请咕咕的作者喝杯咖啡吧QAQ