fork download
copy 
  1. import std.conv, std.functional, std.range, std.stdio, std.string;
  2. import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
  3. import core.bitop;
  4.  
  5. class EOFException : Throwable { this() { super("EOF"); } }
  6. string[] tokens;
  7. string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
  8. int readInt() { return readToken.to!int; }
  9. long readLong() { return readToken.to!long; }
  10. real readReal() { return readToken.to!real; }
  11.  
  12. bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
  13. bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }
  14.  
  15. 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; }
  16. int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
  17. int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }
  18.  
  19.  
  20. struct ModInt(uint M_) {
  21.   import std.conv : to;
  22.   alias M = M_;
  23.   uint x;
  24.   this(ModInt a) { x = a.x; }
  25.   this(uint x_) { x = x_ % M; }
  26.   this(ulong x_) { x = x_ % M; }
  27.   this(int x_) { x = ((x_ %= cast(int)(M)) < 0) ? (x_ + cast(int)(M)) : x_; }
  28.   this(long x_) { x = cast(uint)(((x_ %= cast(long)(M)) < 0) ? (x_ + cast(long)(M)) : x_); }
  29.   ref ModInt opAssign(T)(inout(T) a) if (is(T == uint) || is(T == ulong) || is(T == int) || is(T == long)) { return this = ModInt(a); }
  30.   ref ModInt opOpAssign(string op, T)(T a) {
  31.     static if (is(T == ModInt)) {
  32.       static if (op == "+") { x = ((x += a.x) >= M) ? (x - M) : x; }
  33.       else static if (op == "-") { x = ((x -= a.x) >= M) ? (x + M) : x; }
  34.       else static if (op == "*") { x = cast(uint)((cast(ulong)(x) * a.x) % M); }
  35.       else static if (op == "/") { this *= a.inv(); }
  36.       else static assert(false);
  37.       return this;
  38.     } else static if (op == "^^") {
  39.       if (a < 0) return this = inv()^^(-a);
  40.       ModInt b = this, c = 1U;
  41.       for (long e = a; e; e >>= 1) { if (e & 1) c *= b; b *= b; }
  42.       return this = c;
  43.     } else {
  44.       return mixin("this " ~ op ~ "= ModInt(a)");
  45.     }
  46.   }
  47.   ModInt inv() const {
  48.     uint a = M, b = x; int y = 0, z = 1;
  49.     for (; b; ) { const q = a / b; const c = a - q * b; a = b; b = c; const w = y - cast(int)(q) * z; y = z; z = w; }
  50.     assert(a == 1); return ModInt(y);
  51.   }
  52.   ModInt opUnary(string op)() const {
  53.     static if (op == "+") { return this; }
  54.     else static if (op == "-") { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  55.     else static assert(false);
  56.   }
  57.   ModInt opBinary(string op, T)(T a) const { return mixin("ModInt(this) " ~ op ~ "= a"); }
  58.   ModInt opBinaryRight(string op, T)(T a) const { return mixin("ModInt(a) " ~ op ~ "= this"); }
  59.   bool opCast(T: bool)() const { return (x != 0U); }
  60.   string toString() const { return x.to!string; }
  61. }
  62.  
  63. enum MO = 998244353;
  64. alias Mint = ModInt!MO;
  65.  
  66. enum LIM = 310;
  67. Mint[] inv, fac, invFac;
  68. void prepare() {
  69.   inv = new Mint[LIM];
  70.   fac = new Mint[LIM];
  71.   invFac = new Mint[LIM];
  72.   inv[1] = 1;
  73.   foreach (i; 2 .. LIM) {
  74.     inv[i] = -((Mint.M / i) * inv[cast(size_t)(Mint.M % i)]);
  75.   }
  76.   fac[0] = invFac[0] = 1;
  77.   foreach (i; 1 .. LIM) {
  78.     fac[i] = fac[i - 1] * i;
  79.     invFac[i] = invFac[i - 1] * inv[i];
  80.   }
  81. }
  82. Mint binom(long n, long k) {
  83.   if (n < 0) {
  84.     if (k >= 0) {
  85.       return (-1)^^(k & 1) * binom(-n + k - 1, k);
  86.     } else if (n - k >= 0) {
  87.       return (-1)^^((n - k) & 1) * binom(-k - 1, n - k);
  88.     } else {
  89.       return Mint(0);
  90.     }
  91.   } else {
  92.     if (0 <= k && k <= n) {
  93.       assert(n < LIM);
  94.       return fac[cast(size_t)(n)] * invFac[cast(size_t)(k)] * invFac[cast(size_t)(n - k)];
  95.     } else {
  96.       return Mint(0);
  97.     }
  98.   }
  99. }
  100.  
  101.  
  102. void main() {
  103.   prepare;
  104.   auto S1 = new Mint[][](LIM, LIM);
  105.   foreach (n; 0 .. LIM) {
  106.     S1[n][0] = 0;
  107.     S1[n][n] = 1;
  108.     foreach (k; 1 .. n) {
  109.       S1[n][k] = S1[n - 1][k - 1] + (n - 1) * S1[n - 1][k];
  110.     }
  111.   }
  112.  
  113.   try {
  114.     for (; ; ) {
  115.       const N = readInt();
  116.       auto P = new int[N];
  117.       foreach (i; 0 .. N) {
  118.         P[i] = readInt() - 1;
  119.       }
  120.       auto Q = new int[N];
  121.       foreach (i; 0 .. N) {
  122.         Q[i] = readInt() - 1;
  123.       }
  124.  
  125.       // # cycles of q * p^-1
  126.       auto to = new int[2 * N];
  127.       auto fr = new int[2 * N];
  128.       to[] = -1;
  129.       fr[] = -1;
  130.       void ae(int u, int v) {
  131.     	write("addedge ",u+1);
  132.     	write(" ",v+1);
  133.     	writeln;
  134.         to[u] = v;
  135.         fr[v] = u;
  136.       }
  137.       foreach (i; 0 .. N) {
  138.         if (~P[i]) ae(N + P[i], i);
  139.         if (~Q[i]) ae(i, N + Q[i]);
  140.       }
  141.  
  142.       auto vis = new bool[2 * N];
  143.       int[2][2] cnt;
  144.       foreach (u; 0 .. 2 * N) {
  145.         if (!vis[u] && !~fr[u]) {
  146.           int v = u;
  147.           write("u=",u+1);
  148.           for (; ; v = to[v]) {
  149.             vis[v] = true;
  150.             write(" ",v+1);
  151.             if (!~to[v]) {
  152.               break;
  153.             }
  154.           }
  155.           writeln;
  156.           ++cnt[u / N][v / N];
  157.         }
  158.       }
  159.       int cyc;
  160.       foreach (u; 0 .. 2 * N) {
  161.         if (!vis[u]) {
  162.           for (int v = u; ; ) {
  163.             vis[v] = true;
  164.             if ((v = to[v]) == u) {
  165.               break;
  166.             }
  167.           }
  168.           ++cyc;
  169.         }
  170.       }
  171.        writeln("cnt = ", cnt);
  172.       writeln("cyc = ", cyc);
  173.  
  174.       assert(cnt[0][0] == cnt[1][1]);
  175.  
  176.       /*
  177.         (00 (10)* 11 (01)*)*
  178.         (01)*
  179.         (10)*
  180.         
  181.         (00 (10)* 11) or 01: cnt[0][0] + cnt[0][1]
  182.         10: cnt[1][0] - j
  183.       */
  184.       // nums[k] := # ways for k cycles (10)*
  185.       auto nums = new Mint[N + 1];
  186.       foreach (j; 0 .. cnt[1][0] + 1) {
  187.         foreach (k; 0 .. cnt[1][0] - j + 1) {
  188.           nums[k] += fac[cnt[1][0]] * invFac[cnt[1][0] - j] * binom(j + cnt[0][0] - 1, j) * S1[cnt[1][0] - j][k];
  189.         }
  190.       }
  191.       debug {
  192.         writeln("nums = ", nums);
  193.       }
  194.  
  195.       auto ans = new Mint[N + 1];
  196.       foreach (k; 0 .. N + 1) foreach (l; 0 .. N + 1) {
  197.         if (N - k - l - cyc >= 0) {
  198.           ans[N - k - l - cyc] += S1[cnt[0][0] + cnt[0][1]][k] * nums[l];
  199.         }
  200.       }
  201.       ans[] *= fac[cnt[0][0]];
  202.  
  203.       foreach (k; 0 .. N) {
  204.         if (k > 0) write(" ");
  205.         write(ans[k]);
  206.       }
  207.       writeln;
  208.     }
  209.   } catch (EOFException e) {
  210.   }
  211. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
10
1 2 0 0 0 10 9 6 0 0
2 3 1 0 0 0 8 5 7 0
stdout
copy 
addedge 11 1
addedge 1 12
addedge 12 2
addedge 2 13
addedge 3 11
addedge 20 6
addedge 19 7
addedge 7 18
addedge 16 8
addedge 8 15
addedge 9 17
u=3 3 11 1 12 2 13
u=4 4
u=5 5
u=9 9 17
u=10 10
u=14 14
u=16 16 8 15
u=19 19 7 18
u=20 20 6
cnt = [[3, 2], [1, 3]]
cyc = 0
0 0 0 0 6 78 390 930 1044 432
https://ideone.com/xXruhX
language:
D (dmd 2.085.0)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!