LoginSignup
2
1

More than 5 years have passed since last update.

@bestfitat

bit　

Last updated at Posted at 2018-12-16

https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361 と同じ内容です。

45 AND 25という演算を考える。
45 = 0b101101
25 = 0b011001
なので、
45 AND 25 = 0b001001
すなわち
45 AND 25 = 9
演算子&

#include <iostream>
using namespace std;
int main() {
    int a = 45; // 実際上は 0b101101、あるいは 0x2d と書く
    int b = 25;
    cout << a << " AND " << b << " = " << (a&b) << endl;
}

45 AND 25 = 9

ORは二進法表記したときに各桁ごとにORをとったものになる。

45 = 0b101101
25 = 0b011001
より
45 OR 25 = 0b111101 = 61
になります。演算子|

#include <iostream>
using namespace std;
int main() {
    int a = 45; // 実際上は 0b101101、あるいは 0x2d と書く
    int b = 25;
    cout << a << " OR " << b << " = " << (a|b) << endl;
}
45 OR 25 = 61

XORは片方だけが真であれば成立する。
演算子は^

   10010010
^) 10100111
-----------
   00110101

同じ値で二回XORするともとの値に戻るという性質がある。
a^b^b →　a
a^b^a →　b

NOTは0と1を逆にする。
演算子は~

https://qiita.com/7shi/items/41d262ca11ea16d85abc
https://qiita.com/7shi/items/41d262ca11ea16d85abc
まとまってるサイト

std::bitsetを用いるとより見やすい出力ができる。

#include <iostream>
#include <bitset>
using namespace std;

int main() {
    int A = 0x2d;//0xは16進数
    int B = 0x19;
    cout << A << " AND " << B << " = " << (A&B) << endl;
    cout << bitset<8>(A) << " AND " << bitset<8>(B) << " = " << bitset<8>(A&B) << endl;
}
45 AND 25 = 9
00101101 AND 00011001 = 00001001

左シフト 演算子<<指定した桁だけ左にずらして空いたビットには0が入ります
bin(5<<0) '0b101'
bin(5<<1) '0b1010'
bin(5<<2) '0b10100'
bin(5<<3) '0b101000'
右シフト 演算子>>指定した桁だけ右にずらして、最下位より先に押し出されたビットは消える
bin(5>>0) '0b101'
bin(5>>1) '0b10'
bin(5>>2) '0b1'
bin(5>>3) '0b0'

a番目のフラグが立っている状態は(1<<a)と表せる。さらにa番目とb番目とc番目のフラグが立っている状態は(1<<a)|(1<<b)|(1<<c)と表せる。
ビット演算を用いたフラグ管理
ビットbitにi番目のフラグが立っているかどうか　if(bit&(1<<I))
ビットbitにI番目のフラグが消えているかどうか if(!bit&(1<<I))
ビットbitにI番目のフラグを立てる bit |=(1<<I)
ビットbitにI番目のフラグを消す bit &= ~(1<<I)
ビットbitに何個のフラグが立っているか
_builtin_popcount(bit)
ビットbitにI番目のフラグを立てたもの bit | (1<<I)
ビットbitにI番目のフラグを消したもの
bit & ~(1<<I)

#include <iostream>
#include <bitset>
using namespace std;

const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000

int main() {
    // {1, 3, 5} にフラグの立ったビット
    unsigned int bit = BIT_FLAG_1 | BIT_FLAG_3 | BIT_FLAG_5;
    cout << "{1, 3, 5} = " << bitset<8>(bit) << endl;

    // ビット {1, 3, 5} について、3 番目のフラグが立っていること
    if (bit & BIT_FLAG_3) {
        cout << "3 is in     " << bitset<8>(bit) << endl;
    }

    // ビット {1, 3, 5} について、0 番目のフラグが立っていないこと
    if (!(bit & BIT_FLAG_0)) {
        cout << "0 is not in " << bitset<8>(bit) << endl;
    }

    // 新たなビット
    unsigned int bit2 = BIT_FLAG_0 | BIT_FLAG_3 | BIT_FLAG_4; // {0, 3, 4}
    cout << bitset<8>(bit) << " AND " << bitset<8>(bit2) << " = " << bitset<8>(bit & bit2) << endl; // {1, 3, 5} AND {0, 3, 4} = {3}
    cout << bitset<8>(bit) << " OR  " << bitset<8>(bit2) << " = " << bitset<8>(bit | bit2) << endl; // {1, 3, 5} OR {0, 3, 4} = {0, 1, 3, 4, 5}

    // bit に 6 番目のフラグを立てる
    cout << "before: " << bitset<8>(bit) << endl;
    bit |= BIT_FLAG_6;
    cout << "after : " << bitset<8>(bit) << " (6 included)" << endl;

    // bit2 から 3 番目のフラグを消す
    cout << "before: " << bitset<8>(bit2) << endl;
    bit2 &= ~BIT_FLAG_3;
    cout << "after : " << bitset<8>(bit2) << " (3 excluded)" << endl;

    return 0;
}

{1, 3, 5} = 00101010
3 is in     00101010
0 is not in 00101010
00101010 AND 00011001 = 00001000
00101010 OR  00011001 = 00111011
before: 00101010
after : 01101010 (6 included)
before: 00011001
after : 00010001 (3 excluded)

負の数は補数表現で表す。左端が１の時、負の数となる。その絶対値からすべてのbitを反転させ、１を加えた結果を２の補数という。

マスクビット、、複数のフラグをまとめて立てる、複数のフラグをまとめて消す、必要な情報だけを取り出すためにマスクした部分の情報のみを取り出す。
以下、簡単な例

#include <iostream>
#include <bitset>
using namespace std;

const unsigned int BIT_FLAG_DAMAGE = (1 << 0); // HP が満タンでないか
const unsigned int BIT_FLAG_DOKU = (1 << 1); // 毒状態になっているか
const unsigned int BIT_FLAG_MAHI = (1 << 2); // 麻痺状態になっているか
const unsigned int BIT_FLAG_SENTOFUNO = (1 << 3); // 戦闘不能状態になっているか

// atack して、単にダメージを受ける
const unsigned int MASK_ATTACK = BIT_FLAG_DAMAGE;

// punch して、ダメージも受けて、麻痺もする
const unsigned int MASK_PUNCH = BIT_FLAG_DAMAGE | BIT_FLAG_MAHI;

// defeat して、相手の HP を 0 にする
const unsigned int MASK_DEFEAT = BIT_FLAG_DAMAGE | BIT_FLAG_SENTOFUNO;

// 「毒」と「麻痺」を回復させる: ~MASK_DOKU_MAHI をかけることで回復
const unsigned int MASK_DOKU_MAHI = BIT_FLAG_DOKU | BIT_FLAG_MAHI;


int main() {
    // start: 0000, 初期状態
    unsigned int status = 0;
    cout << "start: " << bitset<4>(status) << endl;

    // attacked: 0001 になる
    status |= MASK_ATTACK;
    cout << "attacked: " << bitset<4>(status) << endl;

    // punched: 0101 になる, HPはすでに満タンでないので、BIT_FLAG_DAMAGE の部分は変化なし
    status |= MASK_PUNCH;
    cout << "punched: " << bitset<4>(status) << endl;

    // 「毒」または「麻痺」かどうかを判定する
    if (status & MASK_DOKU_MAHI) {
        cout << "You are doku or mahi." << endl;
    }

    // kaihuku: 0001 にする, HPは回復しない、麻痺は回復する
    status &= ~MASK_DOKU_MAHI;
    cout << "kaihuku: " << bitset<4>(status) << endl;

    // defeat: 1001 にする, 戦闘不能にする
    status |= MASK_DEFEAT;
    cout << "sentofuno: " << bitset<4>(status) << endl;

    // kaihuku: 1001 のまま、戦闘不能状態は回復しない
    status &= ~MASK_DOKU_MAHI;
    cout << "sentofuno no mama: " << bitset<4>(status) << endl;

    return 0;
}
start: 0000
attacked: 0001
punched: 0101
You are doku or mahi.
kaihuku: 0001
sentofuno: 1001
sentofuno no mama: 1001

bit全探索とは、n個の要素からなる集合{0,1,,,,n-1}の部分集合を全て調べ上げる手法のことです。以下のように実施できる

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 5;

    // {0, 1, ..., n-1} の部分集合の全探索
    for (int bit = 0; bit < (1<<n); ++bit)
    {
        /* bit で表される集合の処理を書く */

    }
}

確認する

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 5;

    // {0, 1, ..., n-1} の部分集合の全探索
    for (int bit = 0; bit < (1<<n); ++bit)
    {
        /* bit で表される集合の処理を書く */


        /* きちんとできていることを確認してみる */
        // bit の表す集合を求める
        vector<int> S;
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) { // i が bit に入るかどうか
                S.push_back(i);
            }
        }

        // bit の表す集合の出力
        cout << bit << ": {";
        for (int i = 0; i < (int)S.size(); ++i) {
            cout << S[i] << " ";
        }
        cout << "}" << endl;
    }
}

0: {}
1: {0 }
2: {1 }
3: {0 1 }
4: {2 }
5: {0 2 }
6: {1 2 }
7: {0 1 2 }
8: {3 }
9: {0 3 }
10: {1 3 }
11: {0 1 3 }
12: {2 3 }
13: {0 2 3 }
14: {1 2 3 }
15: {0 1 2 3 }
16: {4 }
17: {0 4 }
18: {1 4 }
19: {0 1 4 }
20: {2 4 }
21: {0 2 4 }
22: {1 2 4 }
23: {0 1 2 4 }
24: {3 4 }
25: {0 3 4 }
26: {1 3 4 }
27: {0 1 3 4 }
28: {2 3 4 }
29: {0 2 3 4 }
30: {1 2 3 4 }
31: {0 1 2 3 4 }

具体的な問題を解きたい
部分和問題
n個の整数 a[0],a[1],…,a[n−1]が与えられる。これらの整数から何個かの整数を選んで総和を Kとすることができるかどうかを判定せよ。
.1<=n<=20
.1<=a[I]<=1000
.1<=K<=1000

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int main() {
    int n;
    int a[25];
    int K;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    cin >> K;
    //全探索---bitは{0,1,,,,,n-1}の2^n通りの部分集合全体を動く
    bool exist = false;
    for (int bit = 0; bit < (1 << n); ++bit) {
        int sum = 0;//部分集合の和
        for (int i = 0; i < n; ++i) {
            if (bit&(1 << i)) {
                sum += a[i];
            }
        }
        if (sum == K)exist = true;
    }
    if (exist)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

bit全探索は{0,1,,,,n-1}の部分集合を列挙するアルゴリズムでした。n=10として、{2,3,5,7}のように必ずしも0,1,,,9のすべてが揃っているわけではない集合が与えられて、その部分集合を列挙する方法を考える。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 10;
    int A = (1<<2) | (1<<3) | (1<<5) | (1<<7); // {A = {2, 3, 5, 7}

    for(int bit = A; ; bit = (bit-1) & A) {
        /* ここに処理を書く */


        // 最後の 0 で break
        if (!bit) break;
    }
}

このように実現できる

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 10;
    int A = (1<<2) | (1<<3) | (1<<5) | (1<<7); // {A = {2, 3, 5, 7}

    for(int bit = A; ; bit = (bit-1) & A) {
        /* ここに処理を書く */


        /* きちんとできていることを確認してみる */
        // bit の表す集合を求める
        vector<int> S;
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) { // i が bit に入るかどうか
                S.push_back(i);
            }
        }

        // bit の表す集合の出力
        cout << bit << ": {";
        for (int i = 0; i < (int)S.size(); ++i) {
            cout << S[i] << " ";
        }
        cout << "}" << endl;

        // 最後の 0 で break
        if (!bit) break;
    }
}

172: {2 3 5 7 }
168: {3 5 7 }
164: {2 5 7 }
160: {5 7 }
140: {2 3 7 }
136: {3 7 }
132: {2 7 }
128: {7 }
44: {2 3 5 }
40: {3 5 }
36: {2 5 }
32: {5 }
12: {2 3 }
8: {3 }
4: {2 }
0: {}

next_combination
今度はn個の要素の集合{0,1,,,n-1}の部分集合のうち、要素数がkのもののみを列挙する方法を考えます。これは以下のように実現できる(k=0のときには動作しないのでその場合は例外処理する必要がある）

#include <iostream>
#include <vector>
using namespace std;

/* next combination */
int next_combination(int sub) {
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}

int main() {
    int n = 5;  // {0, 1, 2, 3, 4} の部分集合を考える
    int k = 3;

    int bit = (1<<k)-1;  // bit = {0, 1, 2}
    for (;bit < (1<<n); bit = next_combination(bit)) {
        /* ここに処理を書く */

    }
}

確かめる

#include <iostream>
#include <vector>
using namespace std;

/* next combination */
int next_combination(int sub) {
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}

int main() {
    int n = 5;  // {0, 1, 2, 3, 4} の部分集合を考える
    int k = 3;

    int bit = (1<<k)-1;  // bit = {0, 1, 2}
    for (;bit < (1<<n); bit = next_combination(bit)) {
        /* ここに処理を書く */


        /* きちんとできていることを確認してみる */
        // bit の表す集合を求める
        vector<int> S;
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) { // i が bit に入るかどうか
                S.push_back(i);
            }
        }

        // bit の表す集合の出力
        cout << bit << ": {";
        for (int i = 0; i < (int)S.size(); ++i) {
            cout << S[i] << " ";
        }
        cout << "}" << endl;
    }
}

7: {0 1 2 }
11: {0 1 3 }
13: {0 2 3 }
14: {1 2 3 }
19: {0 1 4 }
21: {0 2 4 }
22: {1 2 4 }
25: {0 3 4 }
26: {1 3 4 }
28: {2 3 4 }

Xorshift
bitを用いたシンプルな乱数生成方法

#include <iostream>
#include <map>
using namespace std;

unsigned int randInt() {
    static unsigned int tx = 123456789, ty=362436069, tz=521288629, tw=88675123;
    unsigned int tt = (tx^(tx<<11));
    tx = ty; ty = tz; tz = tw;
    return ( tw=(tw^(tw>>19))^(tt^(tt>>8)) );
}

int main() {
    int count[6] = {0};

    for (int i = 0; i < 100000; ++i) {
        int rng = randInt() % 6;
        count[rng]++;
    }

    for (int i = 0; i < 6; ++i) {
        cout << i+1 << ": " << count[i] << " 回" << endl;
    }
    return 0;
}
1: 16602 回
2: 16512 回
3: 16556 回
4: 16689 回
5: 16939 回
6: 16702 回

bit dp

dp[S]:=全体集合{0,1,,,n-1}の部分集合Sについて、その中で順序を最適化した時の、Sの中での最小コスト

dp[S]=min(dp[S-{I}+cost(S{I},I))のような漸化式が立つことが多い
dp[S]=min(dp[S-{I}+cost(S-{I},I))
初期値
dp[0]=0
最終的な最小コスト
dp[(1<<n)-1]
以下例題

巡回セールスマン問題
n
n
個の都市を、好きな都市から出発してちょうど一度ずつすべての都市を訪れたい。一度訪れた都市にはもう一度行くことはできない。所要時間を最短になるようにせよ。なお、街Iからjへと移動するのにかかる時間dist[I][j]が与えられる。
.1<=n<=20
.0<=dist[I][j]<=1000
.dist[I][I]=0
.dist[I][j]=dist[j][I]

dp[S][v]:=全体集合{0,1,,,n-1}の部分集合Sについて、最後がvであるという制約の下で順序を最適化したときの、Sの中での最小コスト
として、
dp[S][v]=min(dp[S-{v}][u]+dist[u][v])
(u∈S-{v})

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int N;
int dist[21][21];
int dp[(1 << 20) + 1][21];//dpテーブルは余裕をもったサイズにする
int rec(int bit, int v) {
    if (dp[bit][v] != -1)return dp[bit][v];
    if (bit == (1 << v)) {
        return dp[bit][v] = 0;//すでに探索済みだったらリターン
    }
    int res = INF;//答えを格納する変数
    int prev_bit = bit & ~(1 << v);//bitのvを除いたもの
    //vの手前のノードとしてuを全探索
    for (int u = 0; u < N; ++u) {
        if (!(prev_bit&(1 << u)))continue;//uがprev_bitになかったらダメ
        if (res > rec(prev_bit, u) + dist[u][v]) {
            res = rec(prev_bit, u) + dist[u][v];
        }
    }
    return dp[bit][v] = res;
}
int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> dist[i][j];
        }
    }

    for (int bit = 0; bit < (1 << N);++bit) {
        for (int v = 0; v < N; ++v) {
            dp[bit][v] = -1;
        }
    }
    int res = INF;
    for (int v = 0; v<N; ++v) {
        if (res > rec((1 << N) - 1, v)) {
            res = rec((1 << N) - 1, v);
        }
    }
    cout << res << endl;
}

A以下の非負整数のうち3が付くまたは3の倍数の数の総数を求める
mod3の値も覚えておく。添え字のI,j,k,lはそれぞれ上位I個の桁を決めた、A未満が確定している、確定した桁の中に3がある。確定部分をmod３した値、である。
条件演算子　式１ ? 式２ : 式３
式1が真であれば式2を実行式1が偽であれば式3を実行
A以下の非負整数のうち３の倍数または３のつくかつ８の倍数でない数がいくつあるか求めたい。１、A以下の非負整数の総数を求める２、A以下の非負整数のうち3の付く数の総数を求める。3、A以下の非負整数のうち3がつくまたは3の倍数の数の総数を求める4、A以下の非負整数のうち３がつくまたは３の倍数かつ8の倍数でない数の総数を求めるという４つの問題を順に解いていく

1,添え字I,jはそれぞれ.上位I個の桁を決めた.A未満が確定しているを表している。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
string A;
int dp[100001][2];
int main() {
    cin >> A;
    int n = A.size();
    dp[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            int x = j ? 9 : A[i] - '0';
            for (int d = 0; d <= x; ++d) {
                dp[i + 1][j || d < x] += dp[i][j];
            }
        }
    }
    int ans = 0;
    for (int j = 0; j < 2; ++j) {
        ans += dp[n][j];
    }
    cout << ans << endl;
    return 0;
}

2,A以下の非負整数のうち、3のつく数の総数を求める
すでに3を使ったかどうかを覚えておけばよい添え字のI,j,kはそれぞれ上位I個の桁を決めた,A未満が確定している,確定した桁の中に3がある。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
string A;
int dp[100001][2][2];
int main() {
    cin >> A;
    int n = A.size();
    dp[0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                int x = j ? 9 : A[i] - '0';
                for (int d = 0; d <= x; ++d) {
                    dp[i + 1][j || d < x][k || d == 3] += dp[i][j][k];
                }
            }
        }
    }
    int ans = 0;
    for (int j = 0; j < 2; ++j) {
        ans += dp[n][j][1];
    }
    cout << ans << endl;
    return 0;
}

添え字のI,j,k,lはそれぞれ上位I個の桁を決めた、A未満が確定している、確定した桁の中に3がある、確定部分をmod３した値、である。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
string A;
int dp[100001][2][2][3];
int main() {
    cin >> A;
    int n = A.size();
    dp[0][0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                for (int l = 0; l < 3; ++l) {
                    int x = j ? 9 : A[i] - '0';
                    for (int d = 0; d <= x; ++d) {
                        dp[i + 1][j || d < x][k || d == 3][(l + d) % 3] += dp[i][j][k][l];
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int j = 0; j < 2; ++j) {
        for (int k = 0; k < 2; ++k) {
            for (int l = 0; l < 3; ++l) {
                if (k || l == 0) {
                    ans += dp[n][j][k][l];
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

添え字mを追加しこれは確定部分をmod８した値である。mod8の求め方はすでに決まっている部分をXとして新しく決めた部分をDとすると10X+Dができあがる。X mod ８の値がmだったら(10X+D)mod 8だから、という考え方で求めている。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
string A;
int dp[100001][2][2][3][8];
int main() {
    cin >> A;
    int n = A.size();
    dp[0][0][0][0] [0]= 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                for (int l = 0; l < 3; ++l) {
                    for (int m = 0; m < 8; ++m) {
                        int x = j ? 9 : A[i] - '0';
                        for (int d = 0; d <= x; ++d) {
                            dp[i + 1][j || d < x][k || d == 3][(l + d) % 3][(m*10+d)%8] += dp[i][j][k][l][m];

                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int j = 0; j < 2; ++j) {
        for (int k = 0; k < 2; ++k) {
            for (int l = 0; l < 3; ++l) {
                for (int m = 0; m < 8; ++m) {
                    if ((k || l == 0) && m != 0) {
                        ans += dp[n][j][k][l][m];
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}
2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1