#1192384 (C++17) No.3762 Glowing Utility Pole

• 問題: No.3762 Glowing Utility Pole
• ユーザー: 👑 Nachia
• 提出日時: 2026-10-09 22:23:28
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 284 ms / 2,000 ms
• コード長: 9,466 bytes
• コンパイル時間: 1,025 ms
• コンパイル使用メモリ: 156,144 KB
• 実行使用メモリ: 9,908 KB
• 最終ジャッジ日時: 2026-10-09 22:23:40
• 合計ジャッジ時間: 5,220 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge4_0

ファイルパターン	結果
sample	AC * 3
other	AC * 47

ソースコード

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

#include <utility>

#include <cassert>
namespace nachia{

// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const { return x; }
    my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; }
    bool operator==(const my_type& r) const { return x == r.x; }
    my_type pow(unsigned long long i) const {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const { return x; }
    int hval() const { return int(x > MOD/2 ? x - MOD : x); }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

} // namespace nachia
using Mint = nachia::StaticModint<998244353>;

Mint solve(ll N, ll M, V<ll> A){
  V<Mint> powM(N+1); powM[0] = 1;
  REP(i,N) powM[i+1] = powM[i] * M;

  V<Mint> Inv(M+1);
  for(ll i=1; i<=M; i++) Inv[i] = Mint(i).inv();

  V<ll> ex;
  REP(i,M) ex.push_back(i);

  Mint ans = 0;

  V<V<Mint>> dp(M+1, V<Mint>(M+2));
  ll sufcnt = 0, precnt = 0;
  REP(i,N) if(A[i] < 0) precnt += 1;
  for(ll i=N-1; i>=0; i--){
    dp[0][0] += powM[sufcnt];
    if(A[i] >= 0){
      ll t = find(ex.begin(), ex.end(), A[i]) - ex.begin();
      rotate(ex.begin(), ex.begin() + t, ex.begin() + t + 1);
      for(ll f=t; f>=0; f--){
        for(ll d=f; d<=M; d++){
          dp[f+1][d+1] += dp[f][d] * (M-d) * Inv[M-f];
          dp[f+1][d] += dp[f][d] * (d-f) * Inv[M-f];
          dp[f][d] = 0;
        }
      }
    } else {
      sufcnt++; precnt--;
      REP(f,M+1){
        for(ll d=M; d>=f; d--){
          dp[f][d+1] += dp[f][d] * (M-d);
          dp[f][d] *= d;
        }
      }
    }

    // for(auto& a : dp){ for(auto b : a) cout << b.val() << " "; cout << endl; } cout << endl;

    REP(f,M+1) ans += dp[f][M] * powM[precnt];
  }

  return ans;
}

void testcase(){
  ll N, M; cin >> N >> M;
  V<ll> A(N); REP(i,N){ cin >> A[i]; A[i]--; }
  Mint ans = solve(N, M, A);
  cout << ans.val() << "\n";
}

Mint naive(ll N, ll M, V<ll> A){
  V<ll> B = A;
  Mint ans= 0;
  auto dfs = [&](auto& dfs, ll p) -> void {
    if(p == N){
      for(ll l=0; l<=N; l++){
        ll bs = 0;
        for(ll r=l+1; r<=N; r++){
          bs |= 1 << B[r-1];
          if(bs == ((1 << M) - 1)) ans += 1;
        }
      }
      return;
    }
    if(A[p] >= 0){
      dfs(dfs, p+1);
    } else {
      REP(k,M){ B[p] = k; dfs(dfs, p+1); }
    }
  };
  dfs(dfs, 0);
  return ans;
}

#include <unordered_map>
#include <cstdint>
#include <array>


namespace nachia{

int Popcount(unsigned long long c){
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x){
    assert(x != 0ull);
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x88888888;
    constexpr u64 mi = 0x11111111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333333322221100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x){
    assert(x != 0ull);
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

}


namespace nachia{

class Xoshiro256pp{
public:

    using i32 = int32_t;
    using u32 = uint32_t;
    using i64 = int64_t;
    using u64 = uint64_t;


private:
    std::array<u64, 4> s;

    // https://prng.di.unimi.it/xoshiro256plusplus.c
    static inline uint64_t rotl(const uint64_t x, int k) noexcept {
        return (x << k) | (x >> (64 - k));
    }
    inline uint64_t gen(void) noexcept {
        const uint64_t result = rotl(s[0] + s[3], 23) + s[0];
        const uint64_t t = s[1] << 17;
        s[2] ^= s[0];
        s[3] ^= s[1];
        s[1] ^= s[2];
        s[0] ^= s[3];
        s[2] ^= t;
        s[3] = rotl(s[3], 45);
        return result;
    }

    // https://xoshiro.di.unimi.it/splitmix64.c
    u64 splitmix64(u64& x) {
        u64 z = (x += 0x9e3779b97f4a7c15);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
        return z ^ (z >> 31);
    }

    // generate x : 0 <= x <= r
    u64 random_unsigned_from_zero(u64 r){
        if(!r) return 0;
        u64 mask = 1ull << MsbIndex(r);
        mask += mask - 1;
        while(true){
            auto res = rng64() & mask;
            if(res <= r) return res;
        }
    }

public:

    void seed(u64 x = 7001){
        assert(x != 0);
        s[0] = x;
        for(int i=1; i<4; i++) s[i] = splitmix64(x);
    }
    
    std::array<u64, 4> getState() const { return s; }
    void setState(std::array<u64, 4> a){ s = a; }

    Xoshiro256pp(){ seed(); }
    
    u64 rng64() { return gen(); }
    u64 operator()(){ return gen(); }

    // generate x : l <= x <= r
    u64 random_unsigned(u64 l,u64 r){
        assert(l<=r);
        return l + random_unsigned_from_zero(r - l);
    }

    // generate x : l <= x <= r
    i64 random_signed(i64 l,i64 r){
        assert(l<=r);
        return (i64)(random_unsigned_from_zero((u64)r - (u64)l) + (u64)l);
    }


    // permute x : n_left <= x <= n_right
    // output r from the front
    template<class Int>
    std::vector<Int> random_nPr(Int n_left, Int n_right, Int r){
        Int n = n_right-n_left;

        assert(n>=0);
        assert(r<=(1ll<<27));
        if(r==0) return {};  
        assert(n>=r-1);

        std::vector<Int> V;
        std::unordered_map<Int,Int> G;
        for(int i=0; i<r; i++){
            Int p = random_signed(i,n);
            Int x = p - G[p];
            V.push_back(x);
            G[p] = p - (i - G[i]);
        }

        for(Int& v : V) v+=n_left;
        return V;
    }

    // shuffle using swaps
    template<class E>
    void shuffle_inplace(std::vector<E>& V){
        size_t N = V.size();
        for(size_t i=1; i<N; i++){
            std::swap(V[i], V[random_unsigned(0, i)]);
        }
    }

    template<class E>
    std::vector<E> shuffled(const std::vector<E>& V){
        auto cp = V;
        shuffle_inplace(cp);
        return cp;
    }

};

} // namespace nachia
#include <random>
#include <chrono>
nachia::Xoshiro256pp rng;
namespace RngInitInstance { struct RngInit { RngInit(){
    unsigned long long seed1 = std::random_device()();
    unsigned long long seed2 = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    auto s = seed1 ^ seed2;
    #ifdef NACHIA
    std::cerr << "seed = " << s << std::endl;
    #endif
    rng.seed(s);
} } a; }

void test(){
  ll N = 3;
  ll M = 2;
  V<ll> A(N);
  REP(i,N) A[i] = rng() % (M+1) - 1;
  auto ans1 = solve(N, M, A);
  auto ans2 = naive(N, M, A);
  if(ans1.val() != ans2.val()){
    cout << N << " " << M << endl;
    for(auto a : A) cout << (a+1) << " "; cout << endl;
    cout << ans1.val() << endl;
    cout << ans2.val() << endl;
    exit(0);
  }
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  // while(1) test();
  testcase();
  return 0;
}