TTPC 2019 L. 多項式の零点の個数
https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_l?lang=ja
Since $(x \bmod 10^K) = 0 \iff (x \bmod 2^K) = 0 \land (x \bmod 5^K) = 0$, we can use brute-force. I got TLE when using non-constexpr mod.
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) #define range(a) a.begin(), a.end() using namespace std; using ll = long long; template<int MOD> struct solver { class mint { int n; public: mint(int n_ = 0) : n(n_) {} explicit operator int() { return n; } friend mint operator-(mint a) { return -a.n + MOD * (a.n != 0); } friend mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; } friend mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; } friend mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; } friend mint &operator+=(mint &a, mint b) { return a = a + b; } friend mint &operator-=(mint &a, mint b) { return a = a - b; } friend mint &operator*=(mint &a, mint b) { return a = a * b; } friend bool operator==(mint a, mint b) { return a.n == b.n; } friend bool operator!=(mint a, mint b) { return a.n != b.n; } friend istream &operator>>(istream &i, mint &a) { return i >> a.n; } friend ostream &operator<<(ostream &o, mint a) { return o << a.n; } }; mint modpow(mint a, long long b) { if (a == 0) return 0; mint res = 1; while (b > 0) { if (b & 1) res *= a; a *= a; b >>= 1; } return res; } string S; mint x; int k; solver(string S_) : S(S_) {} mint eval(mint x_) { k = S.size(); x = x_; return f_expr(); } mint f_expr() { mint r = f_term(); if (k == 0 || (S[k - 1] != '+' && S[k - 1] != '-')) return r; char op = S[k - 1]; k--; mint l = f_expr(); if (op == '+') l += r; else l -= r; return l; } mint f_term() { mint r = f_factor(); if (k == 0 || S[k - 1] != '*') return r; k--; mint l = f_term(); return l * r; } mint f_factor() { if (isdigit(S[k - 1])) { int r = f_number(); if (k == 0 || S[k - 1] != '^') return r % MOD; k--; mint l = f_value(); return modpow(l, r); } else { return f_value(); } } mint f_value() { if (S[k - 1] == ')') { k--; mint v = f_expr(); assert(S[k - 1] == '('); k--; return v; } else if (S[k - 1] == 'x') { k--; return x; } else { return f_number() % MOD; } } int f_number() { int t = 1; int ans = 0; while (k > 0 && isdigit(S[k - 1])) { ans += (S[k - 1] - '0') * t; t *= 10; k--; } return ans; } }; constexpr int power(int n, int k) { if (k == 0) return 1; return n * power(n, k - 1); } template<int K> void solve(string S) { int ans2 = 0; int ans5 = 0; constexpr int two = power(2, K); constexpr int five = power(5, K); solver<two> solver2(S); solver<five> solver5(S); rep(i, two) if (solver2.eval(i) == 0) ans2 += 1; rep(i, five) if (solver5.eval(i) == 0) ans5 += 1; cout << ans2 * ans5 << endl; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int K; string S; cin >> K >> S; switch (K) { case 1: solve<1>(S); break; case 2: solve<2>(S); break; case 3: solve<3>(S); break; case 4: solve<4>(S); break; case 5: solve<5>(S); break; case 6: solve<6>(S); break; case 7: solve<7>(S); break; case 8: solve<8>(S); break; case 9: solve<9>(S); break; } }