usingnamespacestd;typedeflonglongll;constintN=(1e5+10)*4,mo=998244353;inttwo,G[30],nG" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

【CF】438E. The Child and Binary Tree

系統(tǒng) 2075 0

http://codeforces.com/contest/438/problem/E

題意:詢問(wèn)每個(gè)點(diǎn)權(quán)值在 $c_1, c_2, ..., c_m$ 中,總權(quán)值和為 $s$ 的二叉樹(shù)個(gè)數(shù)。請(qǐng)給出每個(gè)$s \in [1,S]$ 對(duì)應(yīng)的答案。($S,m < 10^5$)

      #include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=(1e5+10)*4, mo=998244353;

int two, G[30], nG[30], rev[N];

int ipow(int a, int b) { int x=1; for(; b; b>>=1, a=(ll)a*a%mo) if(b&1) x=(ll)x*a%mo; return x; }

void fft_init() {

	two=ipow(2, mo-2); G[23]=ipow(3, (mo-1)/(1<<23)); nG[23]=ipow(G[23], mo-2);

	for(int i=22; i; --i) G[i]=(ll)G[i+1]*G[i+1]%mo, nG[i]=(ll)nG[i+1]*nG[i+1]%mo;

}

int getlen(int n) {

	int len=1, bl=-1;

	for(; len<n; len<<=1, ++bl);

	for(int i=1; i<len; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<bl);

	return len;

}

void fft(int *a, int n, int f) {

	for(int i=0; i<n; ++i) if(i<rev[i]) swap(a[i], a[rev[i]]);

	for(int m=2, now=1; m<=n; m<<=1, ++now) {

		int mid=m>>1, w=1, wn=G[now], u, v; if(f) wn=nG[now];

		for(int i=0; i<n; i+=m, w=1) 

			for(int j=0; j<mid; ++j) {

				u=a[i+j], v=(ll)a[i+j+mid]*w%mo;

				a[i+j]=(u+v)%mo; a[i+j+mid]=(u-v+mo)%mo; w=(ll)w*wn%mo;

			}

	}

}

void getinv(int *a, int *b, int n) {

	if(n==1) { b[0]=ipow(a[0], mo-2); return; }

	getinv(a, b, (n+1)>>1);

	static int c[N], d[N];

	memcpy(c, a, sizeof(int)*(n)); memcpy(d, b, sizeof(int)*((n+1)>>1));

	int len=getlen(n+n-1), nlen=ipow(len, mo-2);

	fft(c, len, 0); fft(d, len, 0);

	for(int i=0; i<len; ++i) d[i]=(ll)d[i]*(2-(ll)d[i]*c[i]%mo+mo)%mo;

	fft(d, len, 1);

	for(int i=0; i<n; ++i) b[i]=(ll)d[i]*nlen%mo;

	memset(c, 0, sizeof(int)*(len)); memset(d, 0, sizeof(int)*(len));

}

void getroot(int *a, int *b, int n) {

	if(n==1) { b[0]=sqrt(a[0]); return; }

	getroot(a, b, (n+1)>>1);

	static int c[N], d[N];

	memcpy(c, a, sizeof(int)*(n));

	getinv(b, d, n);

	int len=getlen(n+n-1), nlen=ipow(len, mo-2);

	fft(c, len, 0); fft(d, len, 0);

	for(int i=0; i<len; ++i) d[i]=(ll)c[i]*d[i]%mo;

	fft(d, len, 1);

	for(int i=0; i<n; ++i) b[i]=(ll)two*((b[i]+(ll)d[i]*nlen%mo)%mo)%mo;

	memset(d, 0, sizeof(int)*(len)); memset(c, 0, sizeof(int)*(len));

}

int a[N], b[N];

int main() {

	fft_init();

	int m, n; scanf("%d%d", &n, &m);

	for(int i=0; i<n; ++i) { int x; scanf("%d", &x); if(x<=m) a[x]=mo-4; }

	a[0]=1;

	getroot(a, b, m+1);

	b[0]=(b[0]+1)%mo;

	getinv(b, a, m+1);

	for(int i=1; i<=m; ++i) printf("%d\n", (a[i]<<1)%mo);

	return 0;

}


    

多項(xiàng)式求根= =具體看picks博客..http://picks.logdown.com/posts/202388-square-root-of-polynomial

其實(shí)想到了母函數(shù)然后知道用倍增來(lái)求根本題就解決了= =...跪跪跪orz

一定要注意那些多項(xiàng)式的次數(shù)啊!!!一定要想明白啊!!!

【CF】438E. The Child and Binary Tree


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 天天躁狠狠躁 | 欧美成人一区二免费视频 | 九九久久久久久久爱 | 91在线精品免费观看 | 欧美一区二区三区高清视频 | 精品久久久久久久免费加勒比 | 91手机视频在线 | 女人夜色黄网在线观看 | 亚洲最新在线 | 中文字幕精品一区二区三区视频 | 亚洲精品久久久久久动漫剧情 | 俄罗斯一级成人毛片 | 亚洲视频国产视频 | 欧美特黄级乱色毛片 | 一区 在线播放 | 亚洲国产欧美在线不卡中文 | 国产高清精品91在线 | 国内在线精品 | 九九全国免费视频 | 狠狠躁夜夜躁人人爽天天不 | 国产二区在线播放 | 免费看美女吃男生私人部位 | 奇米网7777 | 久久不卡一区二区三区 | 日本不卡免费一区 | 最近中文字幕无吗高清视频 | 精品香蕉99久久久久网站 | 色狠狠色综合吹潮 | 精品香蕉99久久久久网站 | 久久一本精品久久精品66 | 日日摸夜夜爽夜夜爽出水 | 摸一摸操一操 | 亚洲在线视频播放 | 99久久精品国产高清一区二区 | 91九色首页 | 国产在线观看午夜不卡 | 国产成人91高清精品免费 | a一区二区三区视频 | 国产一区视频在线免费观看 | 色综合久久网 | 久久视频精品a线视频在线观看 |