题目描述
小蓝最近在找—些奇怪的数,其奇数数位上是奇数,而偶数数位上是偶数。
同时,这些数的任意 $5$ 个连续数位的和都不大于 $m$。
例如当 $m=9$ 时,$10101$ 和 $12303$ 就是奇怪的数,而 $12345$ 和 $11111$ 则不是。
小蓝想知道一共有多少个长度为 $n$ 的上述的奇怪的数。
你只需要输出答案对 $998244353$ 取模的结果。
输入格式
输入一行包括两个整数 $n,m$,用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于$30%$ 的测评用例,$n≤12$;
对于 $60%$ 的测评用例,$n≤5000$;
对于所有测评用例,$5≤n≤2×10^5,0≤m≤50$。
输入样例:
5 5
输出样例:
6
题目分析
数位$dp$
因为这里要求
其奇数数位上是奇数,而偶数数位上是偶数
因此想到数位$dp$
、
注意,要满足其奇数数位上是奇数,而偶数数位上是偶数 和 的 任意 $5$ 个连续数位的和都不大于 $m$的性质,要控制循环的步长和初始值,可以通过$len$来判断现在的最后四位应该的奇偶顺序。
代码1 $O(n * m^4)$
未优化 $3 / 10$
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20000, M = 10, MOD = 998244353;
int T;
int dp[N][M][M][M][M]; // 第一维存长度,后面存最后四位数字的状态,因为第五位可以循环递推
int n, m;
void solve()
{
int res = 0;
cin >> n >> m;
for (int i = 1; i <= m && i <= 9; i += 2) // 奇偶交替
for (int j = 0; j <= m - i && j <= 9; j += 2)
for (int k = 1; k <= m - i - j && k <= 9; k += 2)
for (int l = 0; l <= m - i - j - k && l <= 9; l += 2)
dp[4][i][j][k][l] = 1; // 只有这几种状态是合法的,其余状态均不合法,不计入总方案
for (int len = 5; len <= n; len++)
for (int i = (len + 1) % 2; i <= m && i <= 9; i += 2)
for (int j = len % 2; j <= m - i && j <= 9; j += 2)
for (int k = (len + 1) % 2; k <= m - i - j && k <= 9; k += 2)
for (int l = len % 2; l <= m - i - j - k && l <= 9; l += 2)
for (int o = len % 2; o <= m - i - j - k - l && o <= 9; o += 2)
dp[len][i][j][k][o] = (dp[len][i][j][k][o] + dp[len - 1][l][i][j][k]) % MOD;
for (int i = (n + 1) % 2; i <= m && i <= 9; i += 2)
for (int j = n % 2; j <= m - i && j <= 9; j += 2)
for (int k = (n + 1) % 2; k <= m - i - j && k <= 9; k += 2)
for (int l = n % 2; l <= m - i - j - k && l <= 9; l += 2)
res = (res + dp[n][i][j][k][l]) % MOD;
cout << res << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cin >> T;
T = 1;
while (T--)
{
solve();
}
return 0;
}
注:这里怎么循环都行,只要合法即可
比如
for (int len = 5; len <= n; len++)
for (int i = (len + 1) % 2; i <= m && i <= 9; i += 2)
for (int j = len % 2; j <= m - i && j <= 9; j += 2)
for (int k = (len + 1) % 2; k <= m - i - j && k <= 9; k += 2)
for (int o = len % 2; o <= m - i - j - k && o <= 9; o += 2)
for (int l = len % 2; l <= m - i - j - k - o && l <= 9; l += 2)
dp[len][i][j][k][o] = (dp[len][i][j][k][o] + dp[len - 1][l][i][j][k]) % MOD;
逻辑一样,得到的答案也是一样的
可以发现,对于所有数据来说,我们的空间显然不够用,所以第一维度需要降低
所以我们想到了滚动数组。
代码2
滚动数组优化
不开$O(2)$优化会$TLE$
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M = 10, MOD = 998244353;
int T;
int dp[2][M][M][M][M]; // 第一维用滚动数组,后面存最后四位数字的状态,因为第五位可以循环递推
int n, m;
void solve()
{
int res = 0;
cin >> n >> m;
for (int i = 1; i <= m && i <= 9; i += 2) // 奇偶交替
for (int j = 0; j <= m - i && j <= 9; j += 2)
for (int k = 1; k <= m - i - j && k <= 9; k += 2)
for (int l = 0; l <= m - i - j - k && l <= 9; l += 2)
dp[4 % 2][i][j][k][l] = 1; // 只有这几种状态是合法的,其余状态均不合法,不计入总方案
for (int len = 5; len <= n; len++)
{
for (int i = (len + 1) % 2; i <= m && i <= 9; i += 2)
for (int j = len % 2; j <= m - i && j <= 9; j += 2)
for (int k = (len + 1) % 2; k <= m - i - j && k <= 9; k += 2)
for (int l = len % 2; l <= m - i - j - k && l <= 9; l += 2)
for (int o = len % 2; o <= m - i - j - k - l && o <= 9; o += 2)
dp[len % 2][i][j][k][o] = (dp[len % 2][i][j][k][o] + dp[(len - 1) % 2][l][i][j][k]) % MOD;
memset(dp[(len - 1) % 2] , 0 , sizeof(dp[(len - 1) % 2]));
}
for (int i = (n + 1) % 2; i <= m && i <= 9; i += 2)
for (int j = n % 2; j <= m - i && j <= 9; j += 2)
for (int k = (n + 1) % 2; k <= m - i - j && k <= 9; k += 2)
for (int l = n % 2; l <= m - i - j - k && l <= 9; l += 2)
res = (res + dp[n % 2][i][j][k][l]) % MOD;
cout << res << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cin >> T;
T = 1;
while (T--)
{
solve();
}
return 0;
}
这种方式还是很极限,因为需要清零一行的原因,时间上会很紧凑
那怎么进一步优化呢
我们想到了背包问题
从后往前递推不会影响前面的结果
那这道题呢
首先和背包问题一样,我们可以把第一维直接优化掉
dp[i][j][k][o] = (dp[i][j][k][o] + dp[l][i][j][k]) % MOD;
那么怎样不影响结果呢
可以发现,只要我们把更新过的状态保留住,用过的状态清零就行,那么在这里dp[l][i][j][k]
时被用过的,下次更新该状态时一定是下下次循环了,因为奇偶交替的原因,这两个状态一定是互相错开的,正好就形成了滚动数组的状态。
空间优化 $AC$
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M = 10, MOD = 998244353;
int T;
int dp[M][M][M][M]; // 第一维存长度,后面存最后四位数字的状态,因为第五位可以循环递推
int n, m;
void solve()
{
int res = 0;
cin >> n >> m;
for (int i = 1; i <= m && i <= 9; i += 2) // 奇偶交替
for (int j = 0; j <= m - i && j <= 9; j += 2)
for (int k = 1; k <= m - i - j && k <= 9; k += 2)
for (int l = 0; l <= m - i - j - k && l <= 9; l += 2)
dp[i][j][k][l] = 1; // 只有这几种状态是合法的,其余状态均不合法,不计入总方案
for (int len = 5; len <= n; len++)
for (int i = (len + 1) % 2; i <= m && i <= 9; i += 2)
for (int j = len % 2; j <= m - i && j <= 9; j += 2)
for (int k = (len + 1) % 2; k <= m - i - j && k <= 9; k += 2)
for (int l = len % 2; l <= m - i - j - k && l <= 9; l += 2)
{
for (int o = len % 2; o <= m - i - j - k - l && o <= 9; o += 2)
dp[i][j][k][o] = (dp[i][j][k][o] + dp[l][i][j][k]) % MOD;
dp[l][i][j][k] = 0;
}
for (int i = (n + 1) % 2; i <= m && i <= 9; i += 2)
for (int j = n % 2; j <= m - i && j <= 9; j += 2)
for (int k = (n + 1) % 2; k <= m - i - j && k <= 9; k += 2)
for (int l = n % 2; l <= m - i - j - k && l <= 9; l += 2)
res = (res + dp[i][j][k][l]) % MOD;
cout << res << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cin >> T;
T = 1;
while (T--)
{
solve();
}
return 0;
}
Orz,神
tql
神
tql
666