0w1

Digit

CFR 51 D. Beautiful numbers ( Digit DP )

Problem - D - Codeforces題意: 問 [ L, R ] 之間有多少整數,是可以被自身的所有非零數位整除。制約: T ≤ 10 1 ≤ L, R ≤ 9e18解法: 考慮 [ 1, x ] 的動態規劃: 一個顯然的狀態可以這樣定義: dp[ i ][ j ][ k ][ l ]: 考慮前 i 位,模 lcm( 1, 2, .. 9 …

CFR 244 B. Undoubtedly Lucky Numbers ( Digit DP, Python deepcopy() )

Problem - B - Codeforces題意: 給正整數 N,問有多少正整數不超過 N,在十進制下可以用不超過兩種數字表示。資料規模: N ≤ 1e9解法: dp[ i ][ j ][ k ][ l ]: 已處理 N 的長度為 i 的前綴,已使用的數字是 ( j, k ),滿足 j 用 python 的編程瓶頸在於宣…

CFR 431 D. Random Task ( Binary Search, Digit DP )

Problem - 431D - Codeforces題意: 給 M, K。求一個 N,滿足 1 ≤ N ≤ 1e18 且在二進制下,[ N + 1, 2 * N ] 中恰有 M 個數恰有 K 個 1。資料規模: The first line contains two space-separated integers, m and k (0 ≤ m ≤ 1e18; 1 ≤ k ≤ 64).解法: 直覺…

CFR 401 D. Roman and Numbers ( DP, Digit, Bitmask )

Problem - D - Codeforces題意: 給你一個數 N,和 M。求 N 有幾種排列 N',使得 N' 整除 M 且沒有領導零。資料規模: n (1 ≤ n TL: 4000 ms ML: 512 MB解法: 感覺就不太妙。考慮 dp,先有 M 這一維,然後 18 這數字感覺就很數位統計的 fu,在這裡又發現,…

CFR 276 D. Little Girl and Maximum XOR ( Digit XOR DP )

Problem - 276D - Codeforces題意: 給 L, R,求任一對 A, B,滿足 L ≤ A ≤ B ≤ R,可得的最大 A XOR B。數據範圍: 1 ≤ L ≤ R ≤ 1e18解法: 先將 L,R 轉換為二進制,若長度有差則補零在前頭。接著在這上面做動態規劃( 數位統計 )。 dp[ i ][ j ][ k ][ l ]…

CFR 204 A. Little Elephant and Interval ( Digit DP )

Problem - 204A - Codeforces 題意: 求 [ l, r ] 中,第一個位數等於最後一個位數的數字數量。 解法: dp[ i ][ j ][ k ][ l ] : 考慮前 i 個位數,已嚴格小於對照數,第一個位數,最後一個位數,滿足這些條件的狀態數。 注意當 k == 0 的時候若要轉移,那…

CFR Educational 8 D. Magic Numbers ( 桁DP )

Problem - D - Codeforces Just make clear how one state can transfer to another, it will be easy. #include <bits/stdc++.h> using namespace std; const int MAXM = 2000 + 3; const int MAXP = 2000 + 3; const int MOD = 1e9 + 7; #define rep( i, a ) for( int i =</bits/stdc++.h>…

BZOJ 1833 数字计数 ( 桁DP )

Problem 1833. -- [ZJOI2010]count 数字计数 Given a ≤ 1e12, b ≤ 1e12, find frequency for each digit in range [ a , b ]. dp[ i ][ j ][ k ]: chose i digits, less flag, not zero Note that when transferring, we are to add the number of ways of i…

ABC 29 D - 1 ( 桁DP )

D: 1 - AtCoder Beginner Contest 029 | AtCoder 桁DP は応用が利くなぁー(満足) #include <bits/stdc++.h> using namespace std; const int MAXN = 1e9 + 9; const int MAXP = 10; typedef unsigned long long ull; #define rep( i, a ) for(int i = 0; i < (int)( a ); </bits/stdc++.h>…

CFR 635 C. XOR Equation ( 桁DP )

Problem - B - Codeforces pekempey.hatenablog.com pekempeyさんの記事見てやっと通りました。ありがとうございます。これも桁DPが通用するとは思いませんでした、自分もまだまだだなぁ。大きい数のなんとかの方法数を数える時は桁DPをよく考えてみよう。以…

TTPC2015 pF - レシート ( 桁DP )

F: レシート - 東京工業大学プログラミングコンテスト2015 | AtCoder A(1≤A≤10^100)円の商品に対し、X円でそれを購入することができる。買い物の金額A、支払額X、お釣り(X−A)の3つの整数について10進数表記にしたとき、3つの数字が揃う桁の数を最大にしたい…

AOJ Zig-Zag Numbers ( 桁DP )

Zig-Zag Numbers | Aizu Online Judge 一桁の場合はなんだとあれ必ずZig-Zag数という性質上、「今有効一桁だけ」、「今全部0」、「それ以外の状態」と三つに分けてそれぞれ別に判断しなけらばならない。桁dpをする時はleading zeroが方法数にどんな影響を与…

Yuki No.315 世界のなんとか3.5 ( 桁DP )

No.315 世界のなんとか3.5 - yukicoder これは世界のなんとか3のハードバージョン、桁数と余りを取る値が大きすぎて普通にやると状態数がやばい。でもよく考えると、8、80、800の倍数かどうかが決められるのは最後の5桁しかない。よって、最後の5桁…

Introduction to DP on digits ( 桁DP / 數位統計 )

pekempey.hatenablog.com 苦手だったけどpekempeyさんの記事見てよく理解できました、ありがとうございます。pekempeyさんの書き方をモノマネする事になるけどそこはどうか許してください(汗)。 Atcoder Beginner Contest 29 pD. Submission #631749 - AtC…