結果

問題 No.372 It's automatic
ユーザー HaruiHarui
提出日時 2024-05-29 17:44:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 982 ms / 6,000 ms
コード長 5,932 bytes
コンパイル時間 3,327 ms
コンパイル使用メモリ 251,736 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-20 21:04:31
合計ジャッジ時間 16,549 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#line 1 "yuki-372-itsautomatic.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/372"
#line 1 "/home/samejima/CompetitiveProgramming/library/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 1 "/home/samejima/CompetitiveProgramming/library/math/modint.hpp"
template<int MOD>
struct static_modint {
int value;
constexpr static_modint() : value(0) {}
constexpr static_modint(long long v) {
value = int(((v % MOD) + MOD) % MOD);
}
constexpr static_modint& operator+=(const static_modint& other) {
if ((value += other.value) >= MOD) value -= MOD;
return *this;
}
constexpr static_modint& operator-=(const static_modint& other) {
if ((value -= other.value) < 0) value += MOD;
return *this;
}
constexpr static_modint& operator*=(const static_modint& other) {
value = int((long long)value * other.value % MOD);
return *this;
}
constexpr static_modint operator+(const static_modint& other) const {
return static_modint(*this) += other;
}
constexpr static_modint operator-(const static_modint& other) const {
return static_modint(*this) -= other;
}
constexpr static_modint operator*(const static_modint& other) const {
return static_modint(*this) *= other;
}
constexpr static_modint pow(long long exp) const {
static_modint base = *this, res = 1;
while (exp > 0) {
if (exp & 1) res *= base;
base *= base;
exp >>= 1;
}
return res;
}
constexpr static_modint inv() const {
return pow(MOD - 2);
}
constexpr static_modint& operator/=(const static_modint& other) {
return *this *= other.inv();
}
constexpr static_modint operator/(const static_modint& other) const {
return static_modint(*this) /= other;
}
constexpr bool operator!=(const static_modint& other) const {
return val() != other.val();
}
constexpr bool operator==(const static_modint& other) const {
return val() == other.val();
}
int val() const {
return this->value;
}
friend std::ostream& operator<<(std::ostream& os, const static_modint& mi) {
return os << mi.value;
}
friend std::istream& operator>>(std::istream& is, static_modint& mi) {
long long x;
is >> x;
mi = static_modint(x);
return is;
}
};
template <int mod>
using modint = static_modint<mod>;
using modint998244353 = modint<998244353>;
using modint100000007 = modint<1000000007>;
#line 1 "/home/samejima/CompetitiveProgramming/library/dp/automaton/automaton.hpp"
// https://shino16.github.io/blog/post/algo/%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3/
// Dfa
template <typename Alphabet, typename State>
class Dfa {
public:
virtual State init() const = 0; //
virtual State next([[maybe_unused]] State s, [[maybe_unused]] Alphabet a, [[maybe_unused]]int i) const = 0; //
      sa
virtual bool accept([[maybe_unused]] State s) const = 0; // s
virtual bool successful([[maybe_unused]] State s) const { return false; } // nextaccept
virtual bool unsuccessful([[maybe_unused]] State s) const { return false; } // nextaccpet
};
#line 2 "/home/samejima/CompetitiveProgramming/library/dp/automaton/remainder.hpp"
// next
// 使
// M
template <typename Alphabet>
class RemainderAutomaton : public Dfa<Alphabet, int> {
const int M;
const int N_siz;
public:
using State = int;
RemainderAutomaton(int _N_siz, int _M) : M(_M), N_siz(_N_siz) {}
State init() const override {
return State(0);
}
State next(State s, char c, int i) const override {
State ret = ((long long)s*10 + (long long)(c - '0') )%M;
return ret;
}
bool accept(State s) const override {
return s == 0;
}
bool successful ([[maybe_unused]] State s) const override {
return false;
}
bool unsuccessful([[maybe_unused]] State s) const override {
return false;
}
};
#line 6 "yuki-372-itsautomatic.test.cpp"
using mint = modint100000007;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
string S; cin >> S;
vector<char> svec(S.begin(), S.end());
int M; cin >> M;
vector<char> alphabet = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
RemainderAutomaton<char> ra(S.size(), M);
mint ans = 0;
vector<mint>dp1(M), dp2(M);
for (int i = 0; i < S.size(); i++) {
if (S[i] == '0') ans += 1;
else {
dp2[(S[i] - '0') % M] += 1; // only one word substring, 'S[i]' .
}
for (int j = 0; j < M; j++) {
dp2[j] += dp1[j]; // the case when S[i] is not choosed
dp2[(j * 10 + S[i] - '0') % M] += dp1[j]; // the case when S[i] is choosen and added into past substrings
}
swap(dp1, dp2);
dp2.assign(M, 0);
}
for(int i=0; i<M; i++) {
if (ra.accept(i)) ans += dp1[i];
}
cout << ans.val() << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0