相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/03/4237864728368.png
斯特林数相关:https://en.wikipedia.org/wiki/Stirling_number
解题报告
答案显然就是两个序列卷积起来
而其中一个序列就是一个组合数一样的东西
另一个序列则需要处理出第二类斯特林数
众所周知,预处理特殊的第二类斯特林数可以用$NTT$优化
于是就搞两次$NTT$就可以了,时间复杂度$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 600009; const int MOD = 786433; const int RT = 13; int g[N],f[N],POW[N],REV[N],pos[N]; int n1,n2,m,q,vis[N],a[N],b[N]; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline int Pow(int w, int t) { int ret = 1; for (;t;t>>=1,w=(LL)w*w%MOD) if(t&1)ret=(LL)ret*w%MOD; return ret; } inline int C(int a, int b) { if (a > b) return 0; return ((LL)POW[b] * REV[a] % MOD) * REV[b-a] % MOD; } inline void prework() { for (int i=2;i<N;i++) { for (int j=i*2;j<N;j+=i) { vis[j] = 1; } } vis[1] = 1; POW[0] = REV[0] = 1; for (int i=1;i<N;i++) POW[i] = (LL)POW[i-1] * i % MOD; REV[N-1] = Pow(POW[N-1], MOD-2); for (int i=N-2;i;i--) REV[i] = REV[i+1] * (i+1ll) % MOD; } inline void ntt(int *a, int len, int rev = 0) { for (int i=0;i<len;i++) if (pos[i]<i) swap(a[i], a[pos[i]]); for (int l=2;l<=len;l<<=1) { int wn = Pow(RT, MOD / l); if (rev) wn = Pow(wn, MOD-2); for (int i=0,w=1,tmp;i<len;i+=l,w=1) { for (int j=0;j<(l>>1);j++,w=(LL)w*wn%MOD) { tmp = (LL)w * a[i+j+(l>>1)] % MOD; a[i+j+(l>>1)] = (a[i+j] - tmp) % MOD; a[i+j] = (a[i+j] + tmp) % MOD; } } } if (rev) for (int i=1,Rev=Pow(len,MOD-2);i<=len;i++) a[i] = ((LL)a[i] * Rev % MOD + MOD) % MOD; } inline void solve(int l, int *a, int *b) { int t = -1, len = 1; while (len < (l+1)) len <<= 1, t++; for (int i=0;i<len;i++) { pos[i] = pos[i>>1]>>1; if (i&1) pos[i] |= 1<<t; } ntt(a, len); ntt(b, len); for (int i=0;i<len;i++) a[i] = (LL)a[i] * b[i] % MOD; ntt(a, len, 1); } inline void update() { memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for (int i=1;i<=n2;i++) g[i] = (LL)C(i-1, n2-1) * C(i, m) % MOD; for (int i=0;i<=n1;i++) { a[i] = (i&1)? MOD-REV[i]: REV[i]; b[i] = (LL)Pow(i, n1) * REV[i] % MOD; } solve(n1 << 1, a, b); for (int i=1;i<=n1;i++) { if (vis[i]) f[i] = i==n1? 1: C(i-1, n1); else f[i] = a[i]; } } int main() { prework(); for (int T=read();T;T--) { n1 = read(); n2 = read(); m = read(); update(); solve(n1 + n2, f, g); for (int q=read();q;q--) printf("%d\n",(f[read()]+MOD)%MOD); } return 0; }
Heya are using WordPress for your blog platform? I’m new to the blog world but I’m trying to get started and set up my own. Do you
need any coding knowledge to make your own blog?
Any help would be greatly appreciated!
Because the admin of this web page is working, no hesitation very soon it will be renowned, due to its feature
contents.
This paragraph is really a fastidious one it assists new net viewers,
who are wishing in favor of blogging.
I think the admin of this site is in fact working hard in support of his web page, as here
every stuff is quality based stuff.
My partner and I stumbled over here by a different web address and thought I may as
well check things out. I like what I see so now i am following you.
Look forward to looking into your web page repeatedly.
Hi there! I just wanted to ask if you ever have any problems with hackers?
My last blog (wordpress) was hacked and I ended up losing several
weeks of hard work due to no backup. Do you have any solutions to stop hackers?
If some one desires to be updated with newest technologies after that he must
be pay a visit this web site and be up to date everyday.
First of all I would like to say terrific blog! I had a quick question that I’d like to ask if
you don’t mind. I was interested to know how you center yourself and clear your
head before writing. I’ve had a hard time clearing my mind in getting
my thoughts out. I do take pleasure in writing but it just seems like the first 10 to 15 minutes are usually lost simply just trying
to figure out how to begin. Any suggestions or hints?
Thank you!
What’s up i am kavin, its my first occasion to commenting anywhere,
when i read this piece of writing i thought
i could also create comment due to this brilliant post.
hello there and thank you for your info – I have definitely picked up anything
new from right here. I did however expertise several technical issues using this web site,
since I experienced to reload the site lots of times previous to I could get it to load correctly.
I had been wondering if your web host is OK? Not that I am
complaining, but sluggish loading instances times will sometimes affect your placement in google and could damage your high-quality score if ads and marketing with Adwords.
Anyway I am adding this RSS to my email and can look out for
a lot more of your respective intriguing content.
Make sure you update this again soon.
Heya i’m for the first time here. I found this board and I find It really helpful
& it helped me out a lot. I am hoping to give one thing back and
aid others like you aided me.
Great blog! Is your theme custom made or did you download it from somewhere?
A theme like yours with a few simple adjustements would really make my
blog stand out. Please let me know where you got your theme.
Thank you
Wonderful goods from you, man. I have understand your stuff previous
to and you are just extremely fantastic. I really like what you
have acquired here, really like what you are saying and the way in which you say it.
You make it entertaining and you still care for to keep it smart.
I can’t wait to read far more from you. This is really a tremendous
site.
I think the admin of this website is really working hard for his site,
as here every data is quality based stuff.
This is the right blog for anyone who wants to find out about this topic. You realize so much its almost hard to argue with you (not that I actually would want…HaHa). You definitely put a new spin on a topic thats been written about for years. Great stuff, just great!
Do you mind if I quote a couple of your articles as long
as I provide credit and sources back to your site?
My website is in the exact same area of interest as yours and my visitors would definitely benefit
from a lot of the information you provide here. Please let me know if this okay with you.
Regards!
Hey! Do you use Twitter? I’d like to follow you if that would be okay.
I’m absolutely enjoying your blog and look forward to new
updates.
Marvelous, what a weblog it is! This website gives valuable data to
us, keep it up.
If you are going for finest contents like
I do, only pay a quick visit this website every day for
the reason that it provides feature contents, thanks
Hi! This is my 1st comment here so I just wanted to give a quick shout out and tell you I genuinely enjoy reading
through your articles. Can you recommend any other blogs/websites/forums that go over the same subjects?
Thank you!
Excellent post. I used to be checking constantly this weblog and I am impressed!
Very helpful information specifically the ultimate
section 🙂 I deal with such info much. I used to be looking
for this particular info for a long time. Thank you and good luck.
Genuinely no matter if someone doesn’t know after that its up to other users that they will assist, so here
it happens.
Right away I am going to do my breakfast, after having my breakfast coming over again to read other news.
Howdy! I could have sworn I’ve visited this blog before but after going through many of the articles I realized
it’s new to me. Anyhow, I’m definitely pleased I came across it and I’ll be bookmarking it and checking back often!
You are my inhalation, I own few blogs and sometimes run out from to post : (.