結果

問題 No.3415 Dial Lock
コンテスト
ユーザー Kude
提出日時 2025-12-22 02:39:49
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 3,257 ms / 10,000 ms
コード長 3,763 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,094 ms
コンパイル使用メモリ 324,252 KB
実行使用メモリ 24,276 KB
最終ジャッジ日時 2025-12-22 02:41:06
合計ジャッジ時間 67,086 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using mint = static_modint<120586241>;
const mint root = mint(internal::primitive_root<mint::mod()>).pow((mint::mod()-1)/10);
mint pow_r[11];

int p10[6];
mint f[10 * 10 * 10 * 10 * 10];

template<class T>
struct bostan_mori {
  vector<T> p, q;
  bostan_mori(vector<T> &_p, vector<T> &_q) : p(_p), q(_q) {}
  void rev(vector<T> &f) const {
    int d = f.size();
    rep(i, d) if (i&1) f[i] = -f[i];
  }
  void even(vector<T> &f) const {
    int d = (f.size() + 1) >> 1;
    rep(i, d) f[i] = f[i<<1];
    f.resize(d);
  }
  void odd(vector<T> &f) const {
    int d = f.size() >> 1;
    rep(i, d) f[i] = f[i<<1|1];
    f.resize(d);
  }
  T operator[] (ll n) const {
    vector<T> _p(p), _q(q), _q_rev(q);
    rev(_q_rev);
    for (; n; n >>= 1) {
      _p = convolution(move(_p), _q_rev);
      if (n&1) odd(_p);
      else     even(_p);
      _q = convolution(move(_q), move(_q_rev));
      even(_q);
      _q_rev = _q; rev(_q_rev);
    }
    return _p[0] / _q[0];
  }
};

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  rep(i, 11) pow_r[i] = root.pow(i);
  p10[0] = 1;
  rep(i, 5) p10[i+1] = p10[i] * 10;
  int n, k;
  ll t;
  cin >> n >> k >> t;
  int a[5]{};
  rep(i, n) cin >> a[i], a[i] = (10 - a[i]) % 10;
  const mint ik = mint(k).inv();
  rep(_, k) {
    int idx = 0;
    rep(i, n) {
      int r;
      cin >> r;
      idx += r * p10[i];
    }
    f[idx] += ik;
  }
  rep(k, 5) {
    rep(s, p10[5]) if (s / p10[k] % 10 == 0) {
      mint a[10], b[10];
      rep(i, 10) a[i] = f[s + i * p10[k]];
      rep(i, 10) rep(j, 10) b[i] += a[j] * pow_r[(i * j) % 10];
      rep(i, 10) f[s + i * p10[k]] = b[i];
    }
  }
  queue<pair<vector<mint>, vector<mint>>> que;
  rep(s, p10[5]) que.push({{1}, {1, -f[s]}});
  while (que.size() >= 2) {
    auto [f1, g1] = move(que.front()); que.pop();
    auto [f2, g2] = move(que.front()); que.pop();
    auto p1 = convolution(f1, g2);
    auto p2 = convolution(move(f2), g1);
    if (p1.size() < p2.size()) swap(p1, p2);
    rrep(i, p2.size()) p1[i] += p2[i];
    auto q = convolution(move(g1), move(g2));
    que.emplace(move(p1), move(q));
  }
  auto [p0, q0] = move(que.front()); que.pop();
  for (mint mul = mint(p10[5]).inv(); mint& x : p0) x *= mul;

  rep(s, p10[5]) {
    int e = 0;
    rep(i, 5) e += s / p10[i] * a[i];
    que.push({{pow_r[e % 10]}, {1, -f[s]}});
  }
  while (que.size() >= 2) {
    auto [f1, g1] = move(que.front()); que.pop();
    auto [f2, g2] = move(que.front()); que.pop();
    auto p1 = convolution(f1, g2);
    auto p2 = convolution(move(f2), g1);
    if (p1.size() < p2.size()) swap(p1, p2);
    rrep(i, p2.size()) p1[i] += p2[i];
    auto q = convolution(move(g1), move(g2));
    que.emplace(move(p1), move(q));
  }
  auto [p, q] = move(que.front()); que.pop();
  for (mint mul = mint(p10[5]).inv(); mint& x : p) x *= mul;
  p = convolution(move(p), move(q0));
  q = convolution(move(q), move(p0));
  q.emplace_back(0);
  rrep(i, q.size() - 1) q[i+1] -= q[i];
  bostan_mori<mint> bm(p, q);
  mint ans = bm[t];
  cout << ans.val() << '\n';
}
0