結果
| 問題 | No.315 世界のなんとか3.5 |
| コンテスト | |
| ユーザー |
 yagisumi
|
| 提出日時 | 2021-04-01 22:24:44 |
| 言語 | TypeScript (5.7.2) |
| 結果 |
AC
|
| 実行時間 | 906 ms / 2,000 ms |
| コード長 | 6,533 bytes |
| コンパイル時間 | 8,595 ms |
| コンパイル使用メモリ | 229,704 KB |
| 実行使用メモリ | 46,808 KB |
| 最終ジャッジ日時 | 2024-12-31 16:37:17 |
| 合計ジャッジ時間 | 27,299 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 36 |
ソースコード
import * as fs from 'fs'
// import * as readline from 'readline'
// const rl = readline.createInterface({ input: process.stdin, output: process.stdout })
// const ask = (query: string) => new Promise<string>((resolve) => rl.question(query, resolve))
// // Don't forget `rl.close()`.
const INT = Math.floor
declare global {
interface Array<T> {
last(): T | undefined
isEmpty(): boolean
}
}
Array.prototype.last = function () {
return this.length === 0 ? undefined : this[this.length - 1]
}
Array.prototype.isEmpty = function () {
return this.length === 0
}
const bigIntMax = (...args: bigint[]) => args.reduce((m, e) => (e > m ? e : m))
const bigIntMin = (...args: bigint[]) => args.reduce((m, e) => (e < m ? e : m))
const bigIntAbs = (arg: bigint) => (arg < 0 ? -arg : arg)
declare const stdin: number
function read_stdin() {
return fs.readFileSync(process.env.NODE_ENV === 'debug' ? stdin : process.stdin.fd, 'utf8')
}
class Input {
readonly inputs: string[]
private index = 0
constructor(str?: string) {
this.inputs = (str ? str : read_stdin()).split(/\s+/)
}
number() {
return Number(this.inputs[this.index++])
}
numbers(n: number) {
return this.inputs.slice(this.index, (this.index += n)).map(Number)
}
bigint() {
return BigInt(this.inputs[this.index++])
}
bigints(n: number) {
return this.inputs.slice(this.index, (this.index += n)).map(BigInt)
}
word() {
return this.inputs[this.index++]
}
words(n: number) {
return this.inputs.slice(this.index, (this.index += n))
}
}
function array<T>(len: number, init: T): T[] {
return Array(len).fill(init)
}
function array2<T>(h: number, w: number, init: T): T[][] {
return array(h, 0).map(() => array(w, init))
}
function main() {
const input = new Input()
const A_ = input.word()
const B = input.word()
const A = A_.padStart(B.length, '0')
const P = input.number()
const M = 10 ** 9 + 7
const diff: Record<number, number> = { 8: 1, 80: 2, 800: 3 }
const pdiff = diff[P]
const modp_i = B.length - pdiff
const b_max_state = {
mod3: 0,
has3: false,
mod8: 0,
modp: false,
zero: false,
}
const a_max_state = {
mod3: 0,
has3: false,
mod8: 0,
modp: false,
zero: false,
}
let b_count = 0
let a_count = 0
let b_dp = Array(3 * 2 * 8 * 2 * 2).fill(0)
let b_dp2 = Array(3 * 2 * 8 * 2 * 2)
let a_dp = Array(3 * 2 * 8 * 2 * 2).fill(0)
let a_dp2 = Array(3 * 2 * 8 * 2 * 2)
function IDX(mod3: number, has3: boolean, mod8: number, modp: boolean, zero: boolean) {
return (
mod3 * 2 * 8 * 2 * 2 +
(has3 ? 1 : 0) * 8 * 2 * 2 +
mod8 * 2 * 2 +
(modp ? 1 : 0) * 2 +
(zero ? 1 : 0)
)
}
for (let i = 0; i < B.length; i++) {
b_dp2.fill(0)
a_dp2.fill(0)
const b_digit = Number(B[i])
const a_digit = Number(A[i])
const check_m8 = B.length - i <= 2 + pdiff
const limit_m8 = check_m8 ? 8 : 1
const check_zero = B.length - i <= pdiff
const limit_zero = check_zero ? 2 : 1
const limit_mp = check_zero ? 2 : 1
for (let j = 0; j < 10; j++) {
if (j < b_digit) {
const m3 = (b_max_state.mod3 * 10 + j) % 3
const has3 = b_max_state.has3 || j === 3
const m8 = check_m8 ? (b_max_state.mod8 * 10 + j) % 8 : 0
const mp = b_max_state.modp || (i === modp_i ? m8 === 0 : false)
const zero = check_zero ? j === 0 : false
b_dp2[IDX(m3, has3, m8, mp, zero)] += 1
if (i === B.length - 1) {
if (
(m3 === 0 || has3) &&
!(mp && (P === 8 || (j === 0 && (P === 80 || b_max_state.zero))))
) {
b_count += 1
}
}
}
if (j < a_digit) {
const m3 = (a_max_state.mod3 * 10 + j) % 3
const has3 = a_max_state.has3 || j === 3
const m8 = check_m8 ? (a_max_state.mod8 * 10 + j) % 8 : 0
const mp = a_max_state.modp || (i === modp_i ? m8 === 0 : false)
const zero = check_zero ? j === 0 : false
a_dp2[IDX(m3, has3, m8, mp, zero)] += 1
if (i === B.length - 1) {
if (
(m3 === 0 || has3) &&
!(mp && (P === 8 || (j === 0 && (P === 80 || a_max_state.zero))))
) {
a_count += 1
}
}
}
for (let m3 = 0; m3 < 3; m3++) {
for (let has3 = 0; has3 < 2; has3++) {
for (let m8 = 0; m8 < limit_m8; m8++) {
for (let mp = 0; mp < limit_mp; mp++) {
for (let zero = 0; zero < limit_zero; zero++) {
const t3 = (m3 * 10 + j) % 3
const h3 = has3 === 1 || j === 3
const t8 = check_m8 ? (m8 * 10 + j) % 8 : 0
const tp = mp === 1 || (i === modp_i ? t8 === 0 : false)
const t_zero = check_zero ? j === 0 : false
const idx = IDX(t3, h3, t8, tp, t_zero)
const idx0 = IDX(m3, has3 === 1, m8, mp === 1, zero === 1)
b_dp2[idx] = (b_dp2[idx] + b_dp[idx0]) % M
a_dp2[idx] = (a_dp2[idx] + a_dp[idx0]) % M
if (i === B.length - 1) {
if (
(t3 === 0 || h3) &&
!(tp && (P === 8 || (j === 0 && (P === 80 || zero === 1))))
) {
b_count = (b_count + b_dp[idx0]) % M
a_count = (a_count + a_dp[idx0]) % M
}
}
}
}
}
}
}
}
b_max_state.mod3 = (b_max_state.mod3 * 10 + b_digit) % 3
b_max_state.has3 = b_max_state.has3 || b_digit === 3
b_max_state.mod8 = (b_max_state.mod8 * 10 + b_digit) % 8
b_max_state.modp = b_max_state.modp || (i === modp_i ? b_max_state.mod8 === 0 : false)
b_max_state.zero = b_digit === 0
a_max_state.mod3 = (a_max_state.mod3 * 10 + a_digit) % 3
a_max_state.has3 = a_max_state.has3 || a_digit === 3
a_max_state.mod8 = (a_max_state.mod8 * 10 + a_digit) % 8
a_max_state.modp = a_max_state.modp || (i === modp_i ? a_max_state.mod8 === 0 : false)
a_max_state.zero = a_digit === 0
;[b_dp, b_dp2, a_dp, a_dp2] = [b_dp2, b_dp, a_dp2, a_dp]
}
if (
(b_max_state.mod3 === 0 || b_max_state.has3) &&
!(b_max_state.modp && (P === 8 || (b_max_state.zero && (P === 80 || B[B.length - 2] === '0'))))
) {
b_count += 1
}
// console.log({ a_count, b_count })
const r = (b_count - a_count) % M
console.log(r < 0 ? r + M : r)
}
// console.time()
main()
// console.timeEnd()