Editorial for 第2回卬高杯 G問題 - 114514-like number
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
概説
dp[i][j]を「(0埋めしてXと同じ桁数と見なした際に)上からi桁目までの決め方であってXより小さいことが確定しているかつ1,4,5の使用状況がjであるようなもの」とし桁dpのようにして解くことができます。(実装例参照)
(以下では、jは0以上8未満の整数とし、jを2進数で表した時の各桁を各数字の使用/未使用に対応付けています)
C++
C++20
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
string x;
cin >> x;
vector<vector<ll>> dp(x.size(), vector<ll>(8, 0));
int nb = 0;//xを上からi桁目(0-indexed)まで見た時の1,4,5の使用状況
if (x[0] == '1')
nb = 1;
if (x[0] == '4')
{
dp[0][1] = 1;
nb = 2;
}
if (x[0] == '5')
{
dp[0][2] = 1;
dp[0][1] = 1;
nb = 4;
}
for (int i = 1; i < int(x.size()); i++)
{
for (int j = 0; j < 8; j++)
{
// 元々xより小さいことが確定しているi-1桁目までの決め方に1,4,5付加
dp[i][j | 1] += dp[i - 1][j];
dp[i][j | 2] += dp[i - 1][j];
dp[i][j | 4] += dp[i - 1][j];
}
if (x[i] == '1')
{
nb |= 1;
}
if (x[i] == '4')
{
// xとi-1桁目まで等しくi桁目が1であるものの処理
dp[i][nb | 1]++;
nb |= 2;
}
if (x[i] == '5')
{
// xとi-1桁目まで等しくi桁目が1,4であるものの処理
dp[i][nb | 1]++;
dp[i][nb | 2]++;
nb |= 4;
}
// 上からi-1桁目までが0のものに付加(生成)
dp[i][1]++;
dp[i][2]++;
dp[i][4]++;
for (int j = 0; j < 8; j++)
dp[i][j] %= 114514;
}
cout << (dp[x.size() - 1][7] + 1) % 114514 << endl;
}
Comments