[Codeforces Round #250 (Div. 1) -E] The Child and Binary Tree
Codeforcesトランスポートゲート
洛谷トランスミッションゲート
タイトル翻訳
私たちの子供はコンピューター科学が大好きで、特に二叉樹が好きです.n n n個の互いに異なる正の整数を含むシーケンスc[1],c[2],.,c [ n ] c[1],c[2],...,c[n] c[1],c[2],...,c[n].点権付きの二叉木がすべての頂点を満たす重み値が集合{c[1],c[2],.,c[n]}{c[1],c[2],...,c[n]}{c[1],c[2],...,c[n]}にある場合、私たちの子供はそれを神と呼ぶ.そして、ポイント権付きツリーの重み値は、そのすべての頂点の重み値の総和であると考えています.整数m m mを与えて、任意のs(1≦s≦m)s(1lesle m)s(1≦s≦m)に対してs sの重み値の神二叉樹の個数を計算することができますか?どのような2本の二叉木が異なると見なされるかを理解するために、サンプルを参照してください.998244353 998244353 998244353 998244353の型取り後の値について答えを知る必要があります.
入力1行目は2 2 2個の整数n,m(1≦n≦1 0 5;1≦m≦1 0 5)n,m(1le nle 10^5;1le mle 10^5)n,m(1≦n≦105;1≦m≦105)である.2行目はn n n個のスペースで区切られた互いに異なる整数c[1],c[2],.,c [ n ] ( 1 ≤ c [ i ] ≤ 1 0 5 ) c[1],c[2],...,c[n](1\le c[i]\le 10^5) c[1],c[2],...,c[n](1≤c[i]≤105).
m m m m行を出力し、行ごとに整数が1つあります.i i行目は、i i i i神998244353(=7)について答えを出力してください× 17 × 2 23 + 1 = 7 × 17 × 223 + 1 998244353(=7\times 17\times 2^{23}+1=7×17×223+1 998244353(=7×17×223+1=7×17×223+1,質量数)型取り後の結果.
入出力サンプル
サンプル#1を入力:
出力サンプル#1:
サンプル#2を入力:
出力サンプル#2:
入力サンプル#3:
出力サンプル#3:
解題分析
各個別の点の生成関数を考慮すると,明らかにr(x)=Σi∈S x i r(x)=sum_である.{i\in S}x^i r(x)=∑i∈Sxi.
二叉木の構造は再帰的に形成できるので,1つのサブツリーのルートノードに対してその生成関数をF(x)F(x)F(x)F(x)であると明らかにF(x)=r(x)F 2(x)+1 F(x)=r(x)F^2(x)+1 F(x)=r(x)F(x)F(x)=r(x)F(x)+1(空のツリーの場合は単独で計算し,生成関数に入れないので,具体的にはいくつかのステップを押すと分かる).
次式を求めることによりF(x)=1±1−4 r(x)2 r(x)F(x)=frac{1pmsqrt{1−4 r(x)}{2 r(x)}F(x)=2 r(x)1±1−4 r(x)となる.
上の正負がどう取っても、下の2 r(x)2 r(x)2 r(x)は明らかに0 0 0次項がなく、逆を求めることができない.
そして,上下に1∓1−4 r(x)1mpsqrt{1−4 r(x)}1∓1−4 r(x)を同乗すると,F(x)=2 1∓1−4 r(x)F(x)=frac{ 2}{1mpsqrt{1−4 r(x)}F(x)=1∓1−4 r(x)2が得られるので,負の番号を取るとゼロ次項がなく,F(x)F(x)F(x)F(x)F(x)F(x)F(x)F(x)F(x)F(x))の0 0 0次項係数は1 1 1であるべきで,この条件を満たさない.したがって,最後の解は2 1+1−4 r(x)frac{2}{1+sqrt{1−4 r(x)}}1+1−4 r(x)2である.
次にルートをどのように開くかを考えます.F(x)=A(x)F(x)=sqrt{A(x)}F(x)=A(x)またはそのニュートン反復のループとする:F(x)=F 0(x)=F 0(x)−G(F 0(x))G’(F 0(x))F(x)=F_0(x)-frac{G(F_0(x)}{G′(F_0(x)}F(x)=F 0(x)=F 0(x)−G′(F 0(x))G(F 0(x)))=F 2(x)−A(x)=F^2(x)=F^2(x)=F^2(x)−A(x)=F(x)−A(x)=F(x)=F(x)=F(x)=F(x)=F(x)=F 0(x)=F 0(x)−F 0(x)−F 2(x)−A(x)−A(x)2 F 0(x)2(x)−A(x)2(x)2 F 0(x)2(x)F x)F(x)=F_0(x)-\frac{F_0^2(x)-A(x)}{2F_0(x)} F(x)=F0(x)−2F0(x)F02(x)−A(x).
再帰的に処理すればよい.
コードは次のとおりです.
洛谷トランスミッションゲート
タイトル翻訳
私たちの子供はコンピューター科学が大好きで、特に二叉樹が好きです.n n n個の互いに異なる正の整数を含むシーケンスc[1],c[2],.,c [ n ] c[1],c[2],...,c[n] c[1],c[2],...,c[n].点権付きの二叉木がすべての頂点を満たす重み値が集合{c[1],c[2],.,c[n]}{c[1],c[2],...,c[n]}{c[1],c[2],...,c[n]}にある場合、私たちの子供はそれを神と呼ぶ.そして、ポイント権付きツリーの重み値は、そのすべての頂点の重み値の総和であると考えています.整数m m mを与えて、任意のs(1≦s≦m)s(1lesle m)s(1≦s≦m)に対してs sの重み値の神二叉樹の個数を計算することができますか?どのような2本の二叉木が異なると見なされるかを理解するために、サンプルを参照してください.998244353 998244353 998244353 998244353の型取り後の値について答えを知る必要があります.
入力1行目は2 2 2個の整数n,m(1≦n≦1 0 5;1≦m≦1 0 5)n,m(1le nle 10^5;1le mle 10^5)n,m(1≦n≦105;1≦m≦105)である.2行目はn n n個のスペースで区切られた互いに異なる整数c[1],c[2],.,c [ n ] ( 1 ≤ c [ i ] ≤ 1 0 5 ) c[1],c[2],...,c[n](1\le c[i]\le 10^5) c[1],c[2],...,c[n](1≤c[i]≤105).
m m m m行を出力し、行ごとに整数が1つあります.i i行目は、i i i i神998244353(=7)について答えを出力してください× 17 × 2 23 + 1 = 7 × 17 × 223 + 1 998244353(=7\times 17\times 2^{23}+1=7×17×223+1 998244353(=7×17×223+1=7×17×223+1,質量数)型取り後の結果.
入出力サンプル
サンプル#1を入力:
2 3
1 2
出力サンプル#1:
1
3
9
サンプル#2を入力:
3 10
9 4 3
出力サンプル#2:
0
0
1
1
0
2
4
2
6
15
入力サンプル#3:
5 10
13 10 6 4 15
出力サンプル#3:
0
0
0
1
0
1
0
2
0
5
解題分析
各個別の点の生成関数を考慮すると,明らかにr(x)=Σi∈S x i r(x)=sum_である.{i\in S}x^i r(x)=∑i∈Sxi.
二叉木の構造は再帰的に形成できるので,1つのサブツリーのルートノードに対してその生成関数をF(x)F(x)F(x)F(x)であると明らかにF(x)=r(x)F 2(x)+1 F(x)=r(x)F^2(x)+1 F(x)=r(x)F(x)F(x)=r(x)F(x)+1(空のツリーの場合は単独で計算し,生成関数に入れないので,具体的にはいくつかのステップを押すと分かる).
次式を求めることによりF(x)=1±1−4 r(x)2 r(x)F(x)=frac{1pmsqrt{1−4 r(x)}{2 r(x)}F(x)=2 r(x)1±1−4 r(x)となる.
上の正負がどう取っても、下の2 r(x)2 r(x)2 r(x)は明らかに0 0 0次項がなく、逆を求めることができない.
そして,上下に1∓1−4 r(x)1mpsqrt{1−4 r(x)}1∓1−4 r(x)を同乗すると,F(x)=2 1∓1−4 r(x)F(x)=frac{ 2}{1mpsqrt{1−4 r(x)}F(x)=1∓1−4 r(x)2が得られるので,負の番号を取るとゼロ次項がなく,F(x)F(x)F(x)F(x)F(x)F(x)F(x)F(x)F(x)F(x))の0 0 0次項係数は1 1 1であるべきで,この条件を満たさない.したがって,最後の解は2 1+1−4 r(x)frac{2}{1+sqrt{1−4 r(x)}}1+1−4 r(x)2である.
次にルートをどのように開くかを考えます.F(x)=A(x)F(x)=sqrt{A(x)}F(x)=A(x)またはそのニュートン反復のループとする:F(x)=F 0(x)=F 0(x)−G(F 0(x))G’(F 0(x))F(x)=F_0(x)-frac{G(F_0(x)}{G′(F_0(x)}F(x)=F 0(x)=F 0(x)−G′(F 0(x))G(F 0(x)))=F 2(x)−A(x)=F^2(x)=F^2(x)=F^2(x)−A(x)=F(x)−A(x)=F(x)=F(x)=F(x)=F(x)=F(x)=F 0(x)=F 0(x)−F 0(x)−F 2(x)−A(x)−A(x)2 F 0(x)2(x)−A(x)2(x)2 F 0(x)2(x)F x)F(x)=F_0(x)-\frac{F_0^2(x)-A(x)}{2F_0(x)} F(x)=F0(x)−2F0(x)F02(x)−A(x).
再帰的に処理すればよい.
コードは次のとおりです.
#include
", ans[i]);
}