Submission #1778259


Source Code Expand

# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <numeric>
# include <tuple>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
#define ALL(x)    (x).begin(),(x).end()
#define UNIQ(c)   (c).erase(unique(ALL((c))), end((c)))
#define mp        make_pair
#define eb        emplace_back
typedef pair<LL, LL> P;
typedef pair<P, P> PP;
template<typename A, typename B>inline void chmin(A &a, B b) { if (a>b)a = b; }
template<typename A, typename B>inline void chmax(A &a, B b) { if (a<b)a = b; }

const int MOD = 10000;

string s, s1;
int dp[2][3][10][500][501];

int m;

int calc(bool fr, int updw, int pre, int mod, int index) {
	if (index == s.size())return !mod;
	if (dp[fr][updw][pre][mod][index] != -1)return dp[fr][updw][pre][mod][index];
	int ret = 0, end = fr ? 9 : s[index];
	for (int i = 0,u; i <= end; i++) {
		switch (updw) {
		case 0:
			if (pre&&pre == i)continue;
			else if (pre == 0)u = 0;
			else if (pre > i)u = 1;
			else u = 2;
			break;
		case 1:
			if (pre >= i)continue;
			else u = 2;
			break;
		case 2:
			if (pre <= i)continue;
			else u = 1;
			break;
		}
		ret += calc(fr | (i != s[index]), u, i, (mod * 10 + i) % m, index + 1);
	}
	return dp[fr][updw][pre][mod][index] = ret%MOD;
}

int main() {
	cin >> s >> s1 >> m;
	for (int i = 0; i < s.size(); i++)s[i] -= '0';
	for (int i = s.size() - 1; i >= 0; i--) {
		if (s[i] == 0)s[i] = 9;
		else {
			s[i]--;
			break;
		}
	}
	for (int i = 0; i < 2; i++)for (int j = 0; j < 3; j++)for (int k = 0; k < 10; k++)for (int l = 0; l < 500; l++)for (int p = 0; p < 501; p++)dp[i][j][k][l][p] = -1;
	int aans = calc(0, 0, 0, 0, 0);
	s = s1;
	for (int i = 0; i < s.size(); i++)s[i] -= '0';
	for (int i = 0; i < 2; i++)for (int j = 0; j < 3; j++)for (int k = 0; k < 10; k++)for (int l = 0; l < 500; l++)for (int p = 0; p < 501; p++)dp[i][j][k][l][p] = -1;
	int bans = calc(0, 0, 0, 0, 0);
	cout << (bans - aans + MOD) % MOD << endl;
}

Submission Info

Submission Time
Task F - ジグザグ数 (Zig-Zag Numbers)
User M3_cp
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2534 Byte
Status AC
Exec Time 586 ms
Memory 59008 KB

Judge Result

Set Name set01 set02 set03 set04 set05
Score / Max Score 20 / 20 20 / 20 20 / 20 20 / 20 20 / 20
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
set01 data1
set02 data2
set03 data3
set04 data4
set05 data5
Case Name Status Exec Time Memory
data1 AC 26 ms 59008 KB
data2 AC 27 ms 59008 KB
data3 AC 586 ms 59008 KB
data4 AC 212 ms 59008 KB
data5 AC 275 ms 59008 KB