CF438E The Child and Binary Tree

Description

제목 링크
루트 두 갈래 트리가 있는 모든 노드의 권한 값이\(\{c_1, c_2, c_3,..., c_n}\)에 있다면, 우리는 그것을 좋은 두 갈래 트리라고 부르고, 그 권한 값을 모든 점의 권한 값의 합으로 정의합니다.현재 당신은 모든\(s\in[1,m]\)에 대해\(s\)의 서로 다른 좋은 두 갈래 나무의 수량을 계산해야 합니다. 정답은\(998244353\)에 대한 모드입니다.
\(1\le n\le 10^5,1\le m\le 10^5,1\le c_i\le 10^5\)

Solution

분명히 모든\(s\) 를 열거하면\(\log\) 시간 내에 권한 값이\(s\) 인 두 갈래 나무의 수량을 구해야 합니다. 이것은 그다지 현실적이지 않습니다.
그러면 우리는 생성 함수\(G(x)\)를 정의할 수 있으며, 그것의\(i\) 차항 계수로 권치가\(i\)의 서로 다른 좋은 두 갈래 나무의 수량을 표시하고,\(s\in[1,m]\) 때문에 이런 방법은 비교적 가능할 것이다
\(G(x)\)
그 전에\(g_i\) 권한이\(i\) 인 서로 다른 좋은 두 갈래 나무의 수를 설정하고 이동하는 방법을 고려합니다
두 갈래 트리를 구하는 방안이기 때문에 추이 관계는 카트란드 수와 유사합니다. 즉,\[g_i=\sum\limits_{j=1}^{n}\sum\limits_{k=0}^{i-c_j}g_kg_{i-c_j-k}\tag{1}\] 경계\(g_0=1\)
현재 문제는 이렇게 함수를 생성하는 형식으로 쓸 수 없다는 데 있다. 왜냐하면\(1)\)식은\(\{g_n}\)의 생성 함수를 말아서 몇 명씩 뽑아서 새로운 한 자리에 누적하는 것과 같기 때문이다.
몇 분마다 하나씩 뽑아요?
이것은 함수를 구성하여\(\{g_n}\) 의 생성 함수를 곱하면 상술한 효과를 실현할 수 있도록 고려할 수 있음을 알려 준다
사실 이미 구성할 필요가 없습니다.\(\{c_n}\)의 생성 함수\(C(x)\)는 우리의 요구를 만족시킬 수 있습니다. 즉,\[[x^k]C(x)=[k\in\{c_n}]\tag{2}\] 왜 수동으로 계산하는지 알 수 있습니다.
그러면 이제 밝아집니다. 상기 이전을 생성 함수 형식으로 작성합니다\[G(x)=C(x)G^2(x)+1\tag{3}\]\(C(x)\)는 이미 알고 있기 때문에 상수와 같은 것으로 간주합니다. 그러면 이항은 구근 공식을 이용하여\[G(x)=\frac{1\pm\sqrt{1-4C(x)}{2C(x)}\tag{4}\]를 대체하여\(x=0\) 판단해를 얻습니다.\(C(0)=0). (x) =\frac{1-\sqrt{1-4C(x)}{2C(x)}\tag{5}\]
그러나 유감스럽게도 다항식\(F(x)\)에 역원이 존재하는 충분한 조건은\([x^0]F(x)ot=0\)이고\(C(x)\)의 상수 항목은\(0\)이기 때문에 역원은 존재하지 않는다
\(3)\)식으로 돌아가면\(C(x)\)에 역원이 존재하지 않는 이상 분모에 둘 수 없습니다.\(C(x)\)는 2차항의 계수이므로\(G^2(x)\)를 없애는 것을 고려합니다
\(G(x)\)에 역원이 존재하기 때문에 양쪽을\(G(x)\)로 나누어\[\frac{1}{G(x)}=C(x)+\frac{1}{G^2(x)}\tag{6}\]원을 바꾸고\(H(x)=G^{-1}(x)\)를 설정하면 원식은\[H^2(x)-H(x)+C(x)=0\tag{7}\]로 변경할 수 있습니다. m\sqrt{1-4C(x)}{2}\tag{8}\]\(H(x)=G^{-1}(x)\)로 인해\(H(0)=1\),그래서 최종적으로\[H(x)=\frac{1+\sqrt{1-4C(x)}}{2}\tag{9}\]로 풀렸습니다. 그러면 마지막 답은\[G(x)=\frac{2}{1+\sqrt{1-4C(x)}\tag{10}\]입니다. 그리고 완성했습니다. 복잡도\(O(n\logn)\)
중간에 바뀌는 게 재밌다고 할 수 밖에 없어요.
코드는 다음과 같습니다.

#include
#include
#include
using namespace std;
const int N=1e5+10;
const int mod=998244353;
const int G=3;
const int invG=332748118;
int n,m,A,k,c[N<<2],f[N<<2],p[N<<2],g[N<<2],d[N<<2],h[N<<2],q[N<<2],v[N<<2];
inline void Add(int &x,int y){x+=y;x-=x>=mod? mod:0;}
inline int MOD(int x){x-=x>=mod? mod:0;return x;}
inline int Minus(int x){x+=x<0? mod:0;return x;}
inline int fas(int x,int p){int res=1;while(p){if(p&1)res=1ll*res*x%mod;p>>=1;x=1ll*x*x%mod;}return res;}
inline void NTT(int *a,int f){
    for(register int i=0,j=0;ij)swap(a[i],a[j]);
        for(register int l=k>>1;(j^=l)>=1);}
    for(register int i=1;i>1;PINV(a,b,M);
    k=1;while(k<=deg+deg-2)k<<=1;
    for(register int i=0;i>1;Sqrt(a,b,M);
    k=1;while(k<=deg+deg-2)k<<=1;int INV=fas(k,mod-2);
    for(register int i=0;i

다음으로 전송:https://www.cnblogs.com/ForwardFuture/p/11538076.html