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 5312KB
comments (?)
stdin
copy 
98
0 0 83 0 0 0 46 0 0 0 0 0 62 0 0 0 75 0 0 82 0 69 70 0 0 14 30 0 0 0 0 0 90 9 36 0 52 67 88 38 77 0 0 29 13 10 0 0 28 43 98 0 25 0 26 20 60 92 0 0 0 0 8 0 49 0 0 17 27 39 0 22 0 0 0 0 68 21 0 50 0 58 0 0 2 18 0 0 0 85 74 0 45 0 0 0 0 81 
31 39 0 75 25 0 49 89 0 50 0 0 0 0 0 57 72 56 63 0 0 33 30 64 0 0 14 86 19 0 0 0 0 0 0 0 62 15 8 51 0 0 0 0 0 0 45 0 0 0 95 58 27 0 78 0 38 0 0 10 0 0 0 0 0 0 0 54 0 83 0 81 0 41 0 0 0 91 0 0 0 0 0 59 46 13 0 0 0 0 82 12 0 35 93 32 70 94
stdout
copy 
addedge 1 129
addedge 2 137
addedge 181 3
addedge 4 173
addedge 5 123
addedge 144 7
addedge 7 147
addedge 8 187
addedge 10 148
addedge 160 13
addedge 16 155
addedge 173 17
addedge 17 170
addedge 18 154
addedge 19 161
addedge 180 20
addedge 167 22
addedge 22 131
addedge 168 23
addedge 23 128
addedge 24 162
addedge 112 26
addedge 128 27
addedge 27 112
addedge 28 184
addedge 29 117
addedge 188 33
addedge 107 34
addedge 134 35
addedge 150 37
addedge 37 160
addedge 165 38
addedge 38 113
addedge 186 39
addedge 39 106
addedge 136 40
addedge 40 149
addedge 175 41
addedge 127 44
addedge 111 45
addedge 108 46
addedge 47 143
addedge 126 49
addedge 141 50
addedge 196 51
addedge 51 193
addedge 52 156
addedge 123 53
addedge 53 125
addedge 124 55
addedge 55 176
addedge 118 56
addedge 158 57
addedge 57 136
addedge 190 58
addedge 60 108
addedge 106 63
addedge 147 65
addedge 115 68
addedge 68 152
addedge 125 69
addedge 137 70
addedge 70 181
addedge 120 72
addedge 72 179
addedge 74 139
addedge 166 77
addedge 119 78
addedge 78 189
addedge 148 80
addedge 156 82
addedge 84 157
addedge 100 85
addedge 85 144
addedge 116 86
addedge 86 111
addedge 183 90
addedge 172 91
addedge 91 180
addedge 92 110
addedge 143 93
addedge 94 133
addedge 95 191
addedge 96 130
addedge 97 168
addedge 179 98
addedge 98 192
u=1 1 129
u=2 2 137 70 181 3
u=4 4 173 17 170
u=5 5 123 53 125 69
u=6 6
u=8 8 187
u=9 9
u=10 10 148 80
u=11 11
u=12 12
u=14 14
u=15 15
u=16 16 155
u=18 18 154
u=19 19 161
u=21 21
u=24 24 162
u=25 25
u=28 28 184
u=29 29 117
u=30 30
u=31 31
u=32 32
u=36 36
u=42 42
u=43 43
u=47 47 143 93
u=48 48
u=52 52 156 82
u=54 54
u=59 59
u=60 60 108 46
u=61 61
u=62 62
u=64 64
u=66 66
u=67 67
u=71 71
u=73 73
u=74 74 139
u=75 75
u=76 76
u=79 79
u=81 81
u=83 83
u=84 84 157
u=87 87
u=88 88
u=89 89
u=92 92 110
u=94 94 133
u=95 95 191
u=96 96 130
u=97 97 168 23 128 27 112 26
u=99 99
u=100 100 85 144 7 147 65
u=101 101
u=102 102
u=103 103
u=104 104
u=105 105
u=107 107 34
u=109 109
u=114 114
u=115 115 68 152
u=116 116 86 111 45
u=118 118 56
u=119 119 78 189
u=120 120 72 179 98 192
u=121 121
u=122 122
u=124 124 55 176
u=126 126 49
u=127 127 44
u=132 132
u=134 134 35
u=135 135
u=138 138
u=140 140
u=141 141 50
u=142 142
u=145 145
u=146 146
u=150 150 37 160 13
u=151 151
u=153 153
u=158 158 57 136 40 149
u=159 159
u=163 163
u=164 164
u=165 165 38 113
u=166 166 77
u=167 167 22 131
u=169 169
u=171 171
u=172 172 91 180 20
u=174 174
u=175 175 41
u=177 177
u=178 178
u=182 182
u=183 183 90
u=185 185
u=186 186 39 106 63
u=188 188 33
u=190 190 58
u=194 194
u=195 195
u=196 196 51 193
cnt = [[39, 15], [16, 39]]
cyc = 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 561656917 750950756 903635046 640005822 838594694 179702972 210596524 932331640 96653191 191256861 347140049 952555573 650227020 945326019 353779565 285248159 912494884 345108500 279868112 914278531 870603757 326593370 905907263 831736681 406348431 645172260 817045797 819200326 511747747 885909602 383797820 709252869 573638753 803674936 774212482 183301772 963609403 165377573 428841684 745578006 918697045 803024973 939370502 500127895 287107603 131280143 774587756 56959268 611338014 737655724 335149112 420663249 682828960 340089622 407760987 219760670 363537796 507639295 644493582 932701935 265161892 457226809 174252980 367379400 118305617 273980962 489659108 917818381 846011371 729790910
https://ideone.com/AFB6po
language:
D (dmd 2.085.0)
created:
2 days 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!