前言
一道可以简单也可以复杂的题目…
题解
题意是说，把竖式加法的进位从往高位进一位改为进两位，求对于给定的运算结果$n$，有多少种可能的$a,b$在竖式上相加能够得到。
性质
由于更改了进位方式，使得奇数位的加法只会影响奇数位的结果，偶数位同理。
因此，我们完全可以把奇数位和偶数位独立开来，分成两个部分去讨论。
如$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
|
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;
clock_t START_TIME, END_TIME;
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();
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);
}
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
|
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;
clock_t START_TIME, END_TIME;
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;
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';
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();
while(t--)
printf("%lld\n", solve() - 2);
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
|
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;
clock_t START_TIME, END_TIME;
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();
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);
}
return 0;
}
|