2588 字
13 分钟
UOJ50 【UR #3】链式反应
2018-02-28
题解
FFT&NTT
/
生成函数
/
CDQ

著名核物理专家 Picks 最近发现了一种非常适合核裂变的元素叫囧元素。囧元素原子序数为 1024，囧-2333 如果被一个中子撞击后会分裂成 蒟-1234 和 蒻-1098 同时释放出恰好 $2$ 个中子，并且以破坏死光的方式释放光子。

核物理专家 Picks 做实验从来不用实验仪器。他用手指从宇宙中挑选出了 $n$ 个 囧-2333 原子并编号为 $1$ 到 $n$，并用帅气的眼神发射中子撞击了编号为 $1$ 的囧原子，启动了链式反应。

当一个囧-2333原子被中子撞击时，有两种情况。要么这个囧-2333原子变为了囧-2334 并不再参与后续反应，要么囧-2333会进行核裂变，一方面，裂变产生的破坏死光会照射到 $c$ 个不同的囧-2333原子并且这些原子会极为神奇地分解为氢和氦的混合物并不再参与后续反应。另一方面，裂变后产生的 $2$ 个中子会分别撞上两个不同的囧-2333原子。显然被破坏死光照射后就不是囧-2333了，所以不可能又被中子撞上又被破坏死光照射到。

经过反复实验，核物理专家 Picks 终于确定了 $c$ 的范围 $A$，其中 $A$ 是一个非负整数集合。每次破坏死光会照射并影响到的囧-2333原子数量 $c$ 满足 $c \in A$ 。

链式反应时 Picks 会用肉眼观察实验中出现的事件（仅包括中子的撞击和破坏死光的信息），结束后 Picks 会写下实验记录。

但是很不幸 Picks 的实验记录丢失了。他只记得链式反应后没有剩余的囧-2333原子，而且每次一个囧-2333原子核裂变时，中子总是撞击编号比它大的囧-2333原子，破坏死光也总是照射编号比它大的囧-2333原子。

求可能会有多少种不同的实验记录。你需要对于 $n = 1, \dots, n_{max}$ 输出答案。你只用输出答案对 $998244353$（$7 \times 17 \times 2^{23} + 1$，一个质数）取模后的值。

两个实验记录 $T_1$，$T_2$ 被认为是相同的当且仅当：

  1. “编号为 $v$ 的囧-2333分裂产生的中子撞上了编号为 $u$ 的囧-2333” 这个事件在 $T_1$ 中当且仅当这个事件在 $T_2$ 中。
  2. “编号为 $v$ 的囧-2333分裂产生的破坏死光照射了编号为 $u$ 的囧-2333” 这个事件在 $T_1$ 中当且仅当这个事件在 $T_2$ 中。

输入格式

第一行一个正整数 $n_{max}$。

第二行是一个长度为 $n_{max}$ 的01字符串。如果把字符从 $0$ 开始编号，那么第 $i$ 个字符为 $0$ 表示 $i$ 不在集合 $A$ 内，否则表示 $i$ 在集合 $A$ 内。

输出格式

$n_{max}$ 行，如果把行从 $1$ 开始编号，那么第 $i$ 行表示 $n = i$ 时该问题的答案。

样例一

input

5
10100

output#

1
0
1
0
10

explanation

$n = 1$ 时，只有一种实验记录。

$n = 2$ 时，没有可能的实验记录。

$n = 3$ 时，唯一可能的实验记录为：

  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $2$ 的囧-2333。
  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $3$ 的囧-2333。

$n = 4$ 时，没有可能的实验记录。

$n = 5$ 时，有十种可能的实验记录。第一种是：

  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $2$ 的囧-2333。
  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $3$ 的囧-2333。
  • 编号为 $2$ 的囧-2333分裂产生的中子撞上了编号为 $4$ 的囧-2333。
  • 编号为 $2$ 的囧-2333分裂产生的中子撞上了编号为 $5$ 的囧-2333。

第二种是：

  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $2$ 的囧-2333。
  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $4$ 的囧-2333。
  • 编号为 $2$ 的囧-2333分裂产生的中子撞上了编号为 $3$ 的囧-2333。
  • 编号为 $2$ 的囧-2333分裂产生的中子撞上了编号为 $5$ 的囧-2333。

第三种是：

  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $2$ 的囧-2333。
  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $5$ 的囧-2333。
  • 编号为 $2$ 的囧-2333分裂产生的中子撞上了编号为 $3$ 的囧-2333。
  • 编号为 $2$ 的囧-2333分裂产生的中子撞上了编号为 $4$ 的囧-2333。

第四种是：

  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $2$ 的囧-2333。
  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $3$ 的囧-2333。
  • 编号为 $3$ 的囧-2333分裂产生的中子撞上了编号为 $4$ 的囧-2333。
  • 编号为 $3$ 的囧-2333分裂产生的中子撞上了编号为 $5$ 的囧-2333。

第五种是：

  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $2$ 的囧-2333。
  • 编号为 $1$ 的囧-2333分裂产生的中子撞上了编号为 $3$ 的囧-2333。
  • 编号为 $1$ 的囧-2333分裂产生的破坏死光照射了编号为 $4$ 的囧-2333。
  • 编号为 $1$ 的囧-2333分裂产生的破坏死光照射了编号为 $5$ 的囧-2333。

第六种到第十种均与第五种类似。空白太小我就不演示了。

样例二

input

8
10000000

output

1
0
1
0
4
0
34
0

样例三

见样例数据下载

样例四

见样例数据下载

限制与约定

测试点编号$n$
1$n \leq 8$
2$n \leq 100$
3$n \leq 100$
4$n \leq 200$
5$n \leq 5000$
6$n \leq 5000$
7$n \leq 50000$
8$n \leq 50000$
9$n \leq 70000$
10$n \leq 200000$

时间限制：$4\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载

题解#

设f[i]f[i]为nn个节点的树的方案数f[1]=1f[1] = 1
我们设两个中子打中的子树大小为j,k
则答案为f[n]=∑j∑kCn−1jCn−1−jk∗f[j]∗f[k]f[n] = \sum_{j}\sum_{k}C_{n - 1}^{j}C_{n - 1 - j}^{k}*f[j]*f[k]
然后DP有40分

#include <cstdio>
#include <cstring>
#include <algorithm>
# define int long long 
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int MAXN = 1000;
const int MOD = 998244353;
char s[MAXN];
int F[MAXN];
int c[MAXN][MAXN];
int Inv2 = 499122177;
int DP(int x)
{
    if (F[x] != -1) return F[x];
    if (x == 1) return F[x] = 1;
    else F[x] = 0;
    for (int i = 1; i <= x; i++)
        for (int j = 1; j <= x; j++)
            if (x - 1 - i - j >= 0 && s[x - 1 - i - j])
                (F[x] += 1ll * DP(i) * DP(j) % MOD * c[x - 1][i] % MOD * c[x - 1 - i][j] % MOD * Inv2 % MOD) %= MOD;
    return F[x];
}
signed main()
{
    int n = read();
    scanf ("%s", s);
    for (int i = 0; i < n; i++) s[i] -= '0';
    c[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        c[i][0] = 1;
        for (int j = 1; j <= n; j++)
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
    }
    memset (F, -1, sizeof (F));
    for (int i = 1; i <= n; i++) 
        printf ("%d\n", DP(i));
    return 0;
}

建立生成函数
设f(x)f(x)为答案的生成函数
设g(x)g(x)为限制条件的生成函数
则f′(x)=12f2(x)g(x)+1f'(x)=\frac{1}{2}f^{2}(x)g(x)+1
可以CDQ+FFT用0⋯n−10 \cdots n-1的ff来更新f(n)f(n)
时间复杂度O(nlog⁡2n)O(n\log^{2}{n})

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int MAXN = 200005 * 4;
const int MOD = 998244353;
long long pow_mod(long long a, int b)
{
    long long ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return ans;
}
char s[MAXN];
int F[MAXN], FInv[MAXN];
int g[MAXN], f[MAXN], h[MAXN];
int N, Inv;
int rev[MAXN];
int tmp1[MAXN], tmp2[MAXN];
int Init(int x)
{
    N = 1;
    while (N < (x << 1)) N <<= 1;
    for (int i = 1; i < N; i++)
        if (i & 1)
            rev[i] = (rev[i >> 1] >> 1) | (N >> 1);
        else
            rev[i] = (rev[i >> 1] >> 1);
    Inv = pow_mod(N, MOD - 2);
}
void FFt(int *a, int op)
{
    int w, wn, t;
    for (int i = 1; i < N; i++)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int k = 2; k <= N; k <<= 1)
    {
        wn = pow_mod(3, op == 1 ? (MOD - 1) / k : MOD - 1 - (MOD - 1) / k);
        for (int j = 0; j < N; j += k)
        {
            w = 1;
            for (int i = 0; i < (k >> 1); i++, w = 1ll * w * wn % MOD)
            {
                t = 1ll * a[i + j + (k >> 1)] * w % MOD;
                a[i + j + (k >> 1)] = (a[i + j] - t + MOD) % MOD;
                a[i + j] = (a[i + j] + t) % MOD;
            }
        }
    }
    if (op == -1)
        for (int i = 0; i < N; i++)
            a[i] = 1ll * a[i] * Inv % MOD;
}
void Solve(int l, int r)
{
    if (l == r) return;
    int mid = l + r >> 1;
    Solve(l, mid);
    Init(r - l + 1);
    memset (tmp1, 0, N << 2);
    memset (tmp2, 0, N << 2);
    for (int i = l; i <= mid; i++) tmp1[i - l] = f[i];
    for (int i = 0; i <= r - l; i++)
        if (i < l) tmp2[i] = 2 * f[i] % MOD;
        else if (i <= mid) tmp2[i] = f[i];
    FFt(tmp1, 1), FFt(tmp2, 1);
    for (int i = 0; i < N; i++) tmp1[i] = 1ll * tmp1[i] * tmp2[i] % MOD;
    FFt(tmp1, -1);
    for (int i = mid + 1; i <= r; i++) h[i] = (h[i] + tmp1[i - l]) % MOD;
    memset (tmp1, 0, N << 2);
    memset (tmp2, 0, N << 2);
    for (int i = l; i <= mid; i++) tmp1[i - l] = h[i];
    for (int i = 0; i <= r - l; i++) tmp2[i] = g[i];
    FFt(tmp1, 1), FFt(tmp2, 1);
    for (int i = 0; i < N; i++) tmp1[i] = 1ll * tmp1[i] * tmp2[i] % MOD;
    FFt(tmp1, -1);
    for (int i = mid + 1; i <= r; i++) f[i] = (f[i] + 1ll * tmp1[i - l - 1] * F[i - 1] % MOD * FInv[i] % MOD) % MOD;
    Solve(mid + 1, r);
}
int main()
{
    int n = read();
    scanf ("%s", s);
    for (int i = 0; i < n; i++) s[i] -= '0';
    F[0] = 1;
    for (int i = 1; i <= n; i++) F[i] = 1ll * F[i - 1] * i % MOD;
    FInv[n] = pow_mod(F[n], MOD - 2);
    for (int i = n - 1; i >= 0; i--) FInv[i] = 1ll * FInv[i + 1] * (i + 1) % MOD;
    for (int i = 0; i < n; i++) g[i] = 1ll * s[i] * FInv[i] * FInv[2] % MOD;
    f[1] = 1;
    Solve(1, n);
    for (int i = 1; i <= n; i++)
        printf ("%d\n", 1ll * f[i] * F[i] % MOD);
}
UOJ50 【UR #3】链式反应
https://www.nekomio.com/posts/131/
作者
NekoMio
发布于
2018-02-28
许可协议
CC BY-NC-SA 4.0
京ICP备19044785号-1
© 2025 NekoMio. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari