結果

問題 No.260 世界のなんとか3
ユーザー 🍮かんプリン🍮かんプリン
提出日時 2020-02-24 22:12:14
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,864 bytes
コンパイル時間 2,080 ms
コンパイル使用メモリ 165,280 KB
最終ジャッジ日時 2024-04-27 03:05:05
合計ジャッジ時間 2,499 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:74:1: error: ‘make_vec’ function uses ‘auto’ type specifier without trailing return type
   74 | auto make_vec(size_t a, Ts... ts) {
      | ^~~~
main.cpp:74:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

template<long long mod>
struct mint {
private:
    long long x;
public:
    mint(long long x = 0) :x((mod + x) % mod) {}
    mint(std::string &s) {
        long long z = 0;
        for (int i = 0; i < s.size(); i++) {
            z *= 10;
            z += s[i] - '0';
            z %= mod;
        }
        this->x = z;
    }
    mint& operator+=(const mint &a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint &a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint &a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint& operator/=(const mint &a) {
        long long n = mod - 2;
        mint<mod> u = 1, b = a;
        while (n > 0) {
            if (n & 1) {
                u *= b;
            }
            b *= b;
            n >>= 1;
        }
        return *this *= u;
    }
    mint operator+(const mint &a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint &a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint &a) const {
        mint res(*this);
        return res *= a;
    }
    mint operator/(const mint &a) const {
        mint res(*this);
        return res /= a;
    }
    friend std::ostream& operator<<(std::ostream &os, const mint &n) {
        return os << n.x;
    }
    bool operator==(const mint &a) const {
        return this->x == a.x;
    }
};

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    constexpr int MOD = 1e9 + 7;
    string s, t; cin >> s >> t;
    // dp[0][mod3][mod8][3flag][smaller]
    auto dp = make_vec<mint<MOD>>(2, 3, 8, 2, 2);
    auto dp2 = make_vec<mint<MOD>>(2, 3, 8, 2, 2);
    dp[0][0][0][0][0] = 1;
    dp2[0][0][0][0][0] = 1;
    for (int i = 0; i < s.size(); i++) {
        for (int mod3 = 0; mod3 < 3; mod3++) {
            for (int mod8 = 0; mod8 < 8; mod8++) {
                dp[1][(mod3 * 10 + s[i] - '0') % 3][(mod8 * 10 + s[i] - '0') % 8][1][0] += dp[0][mod3][mod8][1][0];
                if (s[i] != '3') dp[1][(mod3 * 10 + s[i] - '0') % 3][(mod8 * 10 + s[i] - '0') % 8][0][0] += dp[0][mod3][mod8][0][0];
                else dp[1][(mod3 * 10 + s[i] - '0') % 3][(mod8 * 10 + s[i] - '0') % 8][1][0] += dp[0][mod3][mod8][0][0];
                for (int k = 0; k < 10; k++) {
                    if (k != 3) {
                        dp[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][0][1] += dp[0][mod3][mod8][0][1];
                        if (k < s[i] - '0') dp[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][0][1] += dp[0][mod3][mod8][0][0];
                    }
                    dp[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][1][1] += dp[0][mod3][mod8][1][1];
                    if (k < s[i] - '0') dp[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][1][1] += dp[0][mod3][mod8][1][0];
                    if (k == 3) dp[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][1][1] += dp[0][mod3][mod8][0][1];
                    if (k == 3 && s[i] > '3') dp[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][1][1] += dp[0][mod3][mod8][0][0];
                }
            }
        }
        dp[0] = dp[1];
        for (int mod3 = 0; mod3 < 3; mod3++) {
            for (int mod8 = 0; mod8 < 8; mod8++) {
                for (int j = 0; j < 2; j++) {
                    for (int k = 0; k < 2; k++) {
                        dp[1][mod3][mod8][j][k] = 0;
                    }
                }
            }
        }
    }
    for (int i = 0; i < t.size(); i++) {
        for (int mod3 = 0; mod3 < 3; mod3++) {
            for (int mod8 = 0; mod8 < 8; mod8++) {
                dp2[1][(mod3 * 10 + t[i] - '0') % 3][(mod8 * 10 + t[i] - '0') % 8][1][0] += dp2[0][mod3][mod8][1][0];
                if (t[i] != '3') dp2[1][(mod3 * 10 + t[i] - '0') % 3][(mod8 * 10 + t[i] - '0') % 8][0][0] += dp2[0][mod3][mod8][0][0];
                else dp2[1][(mod3 * 10 + t[i] - '0') % 3][(mod8 * 10 + t[i] - '0') % 8][1][0] += dp2[0][mod3][mod8][0][0];
                for (int k = 0; k < 10; k++) {
                    if (k != 3) {
                        dp2[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][0][1] += dp2[0][mod3][mod8][0][1];
                        if (k < t[i] - '0') dp2[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][0][1] += dp2[0][mod3][mod8][0][0];
                    }
                    dp2[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][1][1] += dp2[0][mod3][mod8][1][1];
                    if (k < t[i] - '0') dp2[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][1][1] += dp2[0][mod3][mod8][1][0];
                    if (k == 3) dp2[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][1][1] += dp2[0][mod3][mod8][0][1];
                    if (k == 3 && t[i] > '3') dp2[1][(mod3 * 10 + k) % 3][(mod8 * 10 + k) % 8][1][1] += dp2[0][mod3][mod8][0][0];
                }
            }
        }
        dp2[0] = dp2[1];
        for (int mod3 = 0; mod3 < 3; mod3++) {
            for (int mod8 = 0; mod8 < 8; mod8++) {
                for (int j = 0; j < 2; j++) {
                    for (int k = 0; k < 2; k++) {
                        dp2[1][mod3][mod8][j][k] = 0;
                    }
                }
            }
        }
    }
    mint<MOD> ans = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 1; j < 8; j++) {
            for (int k = 0; k < 2; k++) {
                if (i == 0 || k == 1) {
                    ans += dp2[0][i][j][k][0] + dp2[0][i][j][k][1];
                    ans -= dp[0][i][j][k][1];
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}
0