Submission #18997978


Source Code Expand

Copy
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


struct ModInt(int M_) {
  import std.conv : to;
  alias M = M_;
  int x;
  this(ModInt a) { x = a.x; }
  this(long a) { x = cast(int)(a % M); if (x < 0) x += M; }
  ref ModInt opAssign(long a) { return (this = ModInt(a)); }
  ref ModInt opOpAssign(string op)(ModInt a) {
    static if (op == "+") { x += a.x; if (x >= M) x -= M; }
    else static if (op == "-") { x -= a.x; if (x < 0) x += M; }
    else static if (op == "*") { x = cast(int)((cast(long)(x) * a.x) % M); }
    else static if (op == "/") { this *= a.inv(); }
    else static assert(false);
    return this;
  }
  ref ModInt opOpAssign(string op)(long a) {
    static if (op == "^^") {
      if (a < 0) return (this = inv()^^(-a));
      ModInt t2 = this, te = ModInt(1);
      for (long e = a; e > 0; e >>= 1) {
        if (e & 1) te *= t2;
        t2 *= t2;
      }
      x = cast(int)(te.x);
      return this;
    } else return mixin("this " ~ op ~ "= ModInt(a)");
  }
  ModInt inv() const {
    int a = x, b = M, y = 1, z = 0, t;
    for (; ; ) {
      t = a / b; a -= t * b;
      if (a == 0) {
        assert(b == 1 || b == -1);
        return ModInt(b * z);
      }
      y -= t * z;
      t = b / a; b -= t * a;
      if (b == 0) {
        assert(a == 1 || a == -1);
        return ModInt(a * y);
      }
      z -= t * y;
    }
  }
  ModInt opUnary(string op: "-")() const { return ModInt(-x); }
  ModInt opBinary(string op, T)(T a) const {
    return mixin("ModInt(this) " ~ op ~ "= a");
  }
  ModInt opBinaryRight(string op)(long a) const {
    return mixin("ModInt(a) " ~ op ~ "= this");
  }
  bool opCast(T: bool)() const { return (x != 0); }
  string toString() const { return x.to!string; }
}

enum MO = 998244353;
alias Mint = ModInt!MO;


void main() {
  try {
    for (; ; ) {
      const N = readInt();
      const K = readInt();
      
      auto div = new Mint[][](N + 1, N + 1);
      foreach (i; 0 .. N + 1) foreach (j; 1 .. N + 1) {
        div[i][j] = Mint(i) / Mint(j);
      }
      
      auto dp = new Mint[][][][](K + 1, N + 1, N + 1);
      foreach_reverse (i; 0 .. K + 1) {
        foreach (s; 1 .. N + 1) {
          foreach (b; 0 .. s + 1) {
            const a = s - b;
            dp[i][a][b] = new Mint[a + b];
            if (i < K) {
              if (b == 0) {
                dp[i][a][b][] = dp[i + 1][0][a + b][];
              } else {
                const hit = K - (N - (a + b));
                if (hit > 0) {
                  {
                    const prob = div[hit][K - i];
                    const res = dp[i][a][b - 1];
                    foreach (j; 0 .. a) {
                      dp[i][a][b][j] += prob * res[j];
                    }
                    dp[i][a][b][a] += prob;
                    foreach (j; a + 1 .. a + b) {
                      dp[i][a][b][j] += prob * res[j - 1];
                    }
                  }
                  {
                    const prob = 1 - div[hit][K - i];
                    const res = dp[i][a + 1][b - 1];
                    foreach (j; 0 .. a + b) {
                      dp[i][a][b][j] += prob * res[j];
                    }
                  }
                }
              }
            }
          }
        }
      }
      
      foreach (j; 0 .. N) {
        writeln(dp[0][0][N][j]);
      }
    }
  } catch (EOFException e) {
  }
}

Submission Info

Submission Time
Task D - Shopping
User hos_lyric
Language D (LDC 1.20.1)
Score 1300
Code Size 4625 Byte
Status AC
Exec Time 26 ms
Memory 9300 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 28
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, example0.txt, example1.txt, example2.txt
Case Name Status Exec Time Memory
000.txt AC 10 ms 3264 KB
001.txt AC 5 ms 3320 KB
002.txt AC 5 ms 3616 KB
003.txt AC 7 ms 4312 KB
004.txt AC 13 ms 5160 KB
005.txt AC 16 ms 6112 KB
006.txt AC 15 ms 6664 KB
007.txt AC 21 ms 7340 KB
008.txt AC 20 ms 7828 KB
009.txt AC 26 ms 8912 KB
010.txt AC 25 ms 9224 KB
011.txt AC 22 ms 9300 KB
012.txt AC 3 ms 3124 KB
013.txt AC 4 ms 3284 KB
014.txt AC 4 ms 3176 KB
015.txt AC 4 ms 3236 KB
016.txt AC 19 ms 6756 KB
017.txt AC 4 ms 3204 KB
018.txt AC 5 ms 3428 KB
019.txt AC 4 ms 3184 KB
020.txt AC 11 ms 4728 KB
021.txt AC 21 ms 6612 KB
022.txt AC 10 ms 4384 KB
023.txt AC 17 ms 6236 KB
024.txt AC 10 ms 4968 KB
example0.txt AC 3 ms 3312 KB
example1.txt AC 4 ms 3240 KB
example2.txt AC 10 ms 4580 KB