結果
| 問題 |
No.260 世界のなんとか3
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:01:24 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 340 ms / 2,000 ms |
| コード長 | 8,306 bytes |
| コンパイル時間 | 848 ms |
| コンパイル使用メモリ | 73,996 KB |
| 実行使用メモリ | 19,864 KB |
| 最終ジャッジ日時 | 2025-05-14 13:03:34 |
| 合計ジャッジ時間 | 7,023 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <cstring> // For memset
using namespace std;
// Define MOD constant, 10^9 + 7
const long long MOD = 1e9 + 7;
// Global variables used by the DP function
string N_str; // Current upper bound N as a string
char target_type; // Target set identifier: 'A', 'B', or 'I' (for Intersection)
// Memoization table for DP states
// State dimensions: idx, tight, leading_zeros, rem3, rem8, has3
// Maximum length of N is 10000, so idx can go up to 10000. Size 10001 needed.
// Other dimensions are small: 2, 2, 3, 8, 2 respectively.
long long memo[10001][2][2][3][8][2];
// Digit DP function
// Counts numbers x in [1, N] matching properties defined by target_type
// idx: current digit index being processed (from left, 0-based)
// tight: boolean, true if we are restricted by the digits of N, false otherwise
// leading_zeros: boolean, true if we are currently placing leading zeros
// rem3: current number modulo 3
// rem8: current number modulo 8
// has3: boolean, true if the number contains the digit 3
long long dp(int idx, bool tight, bool leading_zeros, int rem3, int rem8, bool has3) {
// Base case: Reached the end of the number string
if (idx == N_str.length()) {
// If the number formed was 0 (all digits were leading zeros), it's not in [1, N].
if (leading_zeros) return 0;
// Check if the formed number satisfies the conditions for the target set
if (target_type == 'A') {
// Set A: x is NOT divisible by 3 AND does NOT contain digit 3
return (rem3 != 0 && !has3);
} else if (target_type == 'B') {
// Set B: x IS divisible by 8
return (rem8 == 0);
} else if (target_type == 'I') { // 'I' for Intersection A intersect B
// Set A intersect B: x is NOT divisible by 3 AND does NOT contain digit 3 AND IS divisible by 8
return (rem3 != 0 && !has3 && rem8 == 0);
}
// Should not reach here if target_type is valid
return 0;
}
// Check memoization table to avoid recomputing states
long long &mem_val = memo[idx][tight][leading_zeros][rem3][rem8][has3];
if (mem_val != -1) {
return mem_val;
}
long long count = 0; // Accumulator for the count, modulo MOD
// Determine the upper limit for the current digit `d`
int limit = tight ? (N_str[idx] - '0') : 9;
// Iterate through possible digits `d` for the current position `idx`
for (int d = 0; d <= limit; ++d) {
// Update the 'tight' constraint for the next recursive call
bool new_tight = tight && (d == limit);
// Handle the logic based on whether we are currently placing leading zeros
if (leading_zeros && d == 0) {
// If still placing leading zeros (current digit is 0), continue with leading_zeros=true
// The state for number 0 is (rem3=0, rem8=0, has3=false)
count = (count + dp(idx + 1, new_tight, true, 0, 0, false)) % MOD;
} else {
// If d > 0 (first non-zero digit) or if we were already past leading zeros
bool new_leading_zeros = false; // State transitions to not having leading zeros
int new_rem3, new_rem8;
bool new_has3;
// Calculate the new state based on whether 'd' is the first non-zero digit
if (leading_zeros) { // `d` is the first non-zero digit
new_rem3 = d % 3;
new_rem8 = d % 8;
new_has3 = (d == 3);
} else { // `d` is a subsequent digit appended to a non-zero prefix
new_rem3 = (rem3 * 10 + d) % 3;
new_rem8 = (rem8 * 10 + d) % 8;
new_has3 = has3 || (d == 3); // Update has3 if d is 3 or if it was already true
}
// Make the recursive call for the next digit position
count = (count + dp(idx + 1, new_tight, new_leading_zeros, new_rem3, new_rem8, new_has3)) % MOD;
}
}
// Store the computed result in the memoization table and return it
return mem_val = count;
}
// Function to calculate the count of numbers up to N (represented by num_str)
// satisfying the problem's condition: Aho AND NOT Seishun.
// Uses the principle of inclusion-exclusion: N - |A U B| = N - (|A| + |B| - |A intersect B|)
long long count_N(string num_str) {
// Base case: If N is "0", the count of numbers in [1, 0] is 0.
if (num_str == "0") {
return 0;
}
N_str = num_str; // Set the global N string for the DP function
// Calculate N modulo MOD. Needed for the final subtraction step.
long long N_mod_MOD = 0;
for (char c : N_str) {
N_mod_MOD = (N_mod_MOD * 10 + (c - '0')) % MOD;
}
// Calculate count for set A: x % 3 != 0 AND not has3
memset(memo, -1, sizeof(memo)); // Initialize memo table with -1
target_type = 'A';
long long count_A = dp(0, true, true, 0, 0, false); // Initial DP call starts at index 0
// Calculate count for set B: x % 8 == 0
memset(memo, -1, sizeof(memo)); // Reset memo table
target_type = 'B';
long long count_B = dp(0, true, true, 0, 0, false);
// Calculate count for set A intersect B: x % 3 != 0 AND not has3 AND x % 8 == 0
memset(memo, -1, sizeof(memo)); // Reset memo table
target_type = 'I';
long long count_A_intersect_B = dp(0, true, true, 0, 0, false);
// Calculate |A union B| = |A| + |B| - |A intersect B| modulo MOD
long long union_count = (count_A + count_B) % MOD;
union_count = (union_count - count_A_intersect_B + MOD) % MOD; // Add MOD before taking modulo to handle potential negative result
// The final count is N - |A union B| modulo MOD.
// This counts numbers x where NOT (A or B) holds.
// NOT A is (x % 3 == 0 OR has3) which is the "Aho" condition.
// NOT B is (x % 8 != 0) which is the "NOT Seishun" condition.
// So we count numbers that are Aho AND NOT Seishun.
long long result = (N_mod_MOD - union_count + MOD) % MOD; // Add MOD before modulo for subtraction
return result;
}
// Function to subtract 1 from a number represented as a string
string subtract_one(string S) {
// Special case: If S is "1", subtracting 1 gives "0"
if (S == "1") {
return "0";
}
int N = S.length();
string temp = S; // Work on a copy of the string
int i = N - 1; // Start from the rightmost digit (least significant)
while (i >= 0) {
if (temp[i] > '0') {
// If the current digit is greater than '0', decrement it
temp[i]--;
// All digits to the right (if any) become '9'
for (int j = i + 1; j < N; ++j) {
temp[j] = '9';
}
// Finished the subtraction process, break the loop
break;
} else { // temp[i] == '0'
// If the current digit is '0', set it to '9' and continue borrowing from the left
temp[i] = '9';
i--; // Move to the next digit to the left
}
}
// Check if the leading digit became '0' after borrowing (e.g., "1000" -> "0999")
// If so, and the original number had more than one digit, remove the leading '0'
if (temp[0] == '0' && N > 1) {
return temp.substr(1); // Return the substring starting from index 1
} else {
// Otherwise, return the modified string
return temp;
}
}
int main() {
// Optimize C++ standard input/output operations for speed
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string A, B; // Input numbers A and B as strings
cin >> A >> B;
// Calculate count of numbers satisfying the condition up to B
long long ans_B = count_N(B);
// Calculate A-1 as a string
string A_minus_1 = subtract_one(A);
// Calculate count of numbers satisfying the condition up to A-1
long long ans_A_minus_1 = count_N(A_minus_1);
// The final answer for the range [A, B] is count(B) - count(A-1)
// Perform calculation modulo MOD, ensuring non-negative result
long long final_ans = (ans_B - ans_A_minus_1 + MOD) % MOD;
// Output the final answer
cout << final_ans << endl;
return 0;
}