【日常小测】生日礼物

相关链接

题目传送门: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;
}

25 thoughts to “【日常小测】生日礼物”

  1. 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!

  2. 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.

  3. 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?

  4. 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!

  5. 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.

  6. 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.

  7. 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.

  8. 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

  9. 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.

  10. 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!

  11. 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!

  12. 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!

  13. 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.

  14. 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!

Leave a Reply

Your email address will not be published. Required fields are marked *