• 周一. 5月 27th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

求第一类斯特林数的一行

admin

11月 28, 2021

考试时太弱了不会。
结果被吊起来打。
学习了一下zzd的博客
首先(Oleft( n^2 ight))的递推十分简单。
但是不够快,
根据(x^{overline{n}}=sum_{k=0}^n left[ n atop k ight] x^k)
可以得出(Oleft(n log^2night))的分治FFT,
但是不够快,
于是可以倍增地搞。
就是一个(log)的了。
贴上丑陋的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=998244353;
const int G=3;
const int LEN=270000;
int rev[LEN],w[LEN];
int L(int x){
    return x>=M?x-M:x;
}
int U(int x){
    return x<0?x+M:x;
}
ll MUL(int x,int y){
    return (ll)x*y%M;
}
int fp(int x,int y){
    int ret=1;
    for (; y; y>>=1,x=MUL(x,x))
	if (y&1) ret=MUL(ret,x);
    return ret;
}
void NTT(int *a,int len){
    for (int i=0; i<len; ++i) rev[i]=rev[i>>1]>>1|(i&1?len>>1:0);
    //for (int i=0; i<len; ++i) cerr<<i<<" "<<rev[i]<<endl;
    for (int i=0; i<len; ++i) if (i>rev[i]) swap(a[i],a[rev[i]]);
    for (int i=1; i<len; i<<=1){
	w[0]=1;
	w[1]=fp(G,(M-1)/(i<<1));
	for (int j=2; j<i; ++j) w[j]=MUL(w[j-1],w[1]);
	for (int j=0; j<len; j+=i<<1)
	    for (int k=j; k<j+i; ++k){
		int x=a[k],y=MUL(a[k+i],w[k-j]);
		a[k]=L(x+y);
		a[k+i]=U(x-y);
	    }
    }
}
void INTT(int *a,int len){
    reverse(a+1,a+len);
    NTT(a,len);
    int ni=fp(len,M-2);
    for (int i=0; i<len; ++i) a[i]=MUL(a[i],ni);
}
//int a[10],b[10];
void MUL(int *a,int lena,int *b,int lenb){
    int u=1;
    for (; u<lena+lenb-1; u<<=1);
    for (int i=0; i<u; ++i) rev[i]=rev[i>>1]>>1|(i&1?u>>1:0);
    for (int i=lena; i<u; ++i) a[i]=0;
    for (int i=lenb; i<u; ++i) b[i]=0;
    NTT(a,u);
    NTT(b,u);
    for (int i=0; i<u; ++i) a[i]=MUL(a[i],b[i]);
    INTT(a,u);
}
int a[LEN],b[LEN],f[LEN],g[LEN],fac[LEN],invfac[LEN];
void calc(int n){
    //cerr<<"CALC"<<n<<endl;
    if (n==1){
	f[1]=1;
	return;
    }
    int d=n>>1;
    calc(d);
    //cerr<<"???"<<endl;
    for (int i=0; i<=d; ++i) a[d-i]=MUL(f[i],fac[i]);
    for (int i=0; i<=d; ++i) b[i]=MUL(fp(d,i),invfac[i]);
    //for (int i=0; i<=d; ++i) cerr<<a[i]<<"a"; cerr<<endl;
    //for (int i=0; i<=d; ++i) cerr<<b[i]<<"b"; cerr<<endl;
    MUL(a,d+1,b,d+1);
    for (int i=0; i<=d; ++i) g[i]=MUL(a[d-i],invfac[i]);

    //for (int i=0; i<=d; ++i) cerr<<a[i]<<"A"; cerr<<endl;
    //for (int i=0; i<=d; ++i) cerr<<g[i]<<"g"; cerr<<endl;
    //for (int i=0; i<=d; ++i) cerr<<f[i]<<"f"; cerr<<endl;
    MUL(f,d+1,g,d+1);
    //for (int i=0; i<=n; ++i) cerr<<f[i]<<"F"; cerr<<endl;
    //cerr<<"N"<<n<<endl;
    if (n&1){
	//cerr<<"IN"<<endl;
	for (int i=n; i; --i) f[i]=L(f[i-1]+MUL(f[i],n-1));
	//cerr<<"OUT"<<endl;
    }
}
int main(){
    /*a[0]=3; a[1]=3; a[2]=2;
    b[0]=5; b[1]=7; b[2]=6;
    int u=1;
    for (; u<5; u<<=1);
    NTT(a,u);
    cerr<<fp(G,(M-1)/4)<<endl;
    for (int i=0; i<u; ++i) cout<<a[i]<<" "; cerr<<endl;
    NTT(b,u);
    for (int i=0; i<u; ++i) a[i]=MUL(a[i],b[i]);
    INTT(a,u);
    for (int i=0; i<u; ++i) cout<<a[i]<<" ";*/
    int n,aa,bb;
    scanf("%d%d%d",&n,&aa,&bb);
    fac[0]=1; for (int i=1; i<=n; ++i) fac[i]=MUL(fac[i-1],i);
    invfac[n]=fp(fac[n],M-2); for (int i=n-1; i>=0; --i) invfac[i]=MUL(invfac[i+1],i+1);
    calc(n);
    int ans=0;
    for (int i=aa; i<=bb; ++i){
	//cerr<<i<<" "<<f[i]<<" "<<ans<<endl;
	ans=L(ans+f[i]);
    }
    cout<<ans;
}

《求第一类斯特林数的一行》有4个想法
  1. Wow, amazing weblog layout! How long have you ever been blogging for?

    you made blogging look easy. The entire look of your web site is wonderful, let alone the content material!
    You can see similar here sklep online

  2. Great blog! Is your theme custom made or did you download it from somewhere?
    A design like yours with a few simple tweeks would really make
    my blog stand out. Please let me know where you got your design. Appreciate it I saw similar here:
    Najlepszy sklep

  3. Hey! This is my first visit to your blog! We are a team of volunteers and starting a new project in a community in the same niche.

    Your blog provided us beneficial information to work
    on. You have done a marvellous job! I saw similar
    here: Najlepszy sklep

  4. Howdy! Do you know if they make any plugins to help with SEO?
    I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very
    good results. If you know of any please share. Many thanks!
    You can read similar art here: Najlepszy sklep

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注