设为首页 加入收藏

TOP

[HEOI2016/TJOI2016] 求和
2019-06-08 22:12:07 】 浏览:17
Tags:HEOI2016/TJOI2016

推式子

\[ f(n)=\sum_{i=0}^n\sum_{j=0}^iS(i,j)\times 2^j\times (j!)\\ =\sum_{i=0}^n\sum_{j=0}^nS(i,j)\times 2^j\times (j!)=\sum_{i=0}^n2^i\times (i!)\sum_{j=0}^n S(j,i) \]

注意到

\[ S(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^iC(m,i)(m-i)^n\\ =\sum_{i=0}^m\frac{(-1)^i\times (m-i)^n}{i!\times (m-i)!} \]

带入得

\[ f(n)=\sum_{i=0}^n2^i\times i!\sum_{j=0}^n\sum_{k=0}^i\frac{(-1)^k\times(i-k)^j}{k!\times (i-k)!}\\ =\sum_{i=0}^n2^i\times i!\sum_{k=0}^i\frac{(-1)^k}{k!}\frac{\sum_{j=0}^n(i-k)^j}{(i-k)!}\\ \]

注意,其中的\(0^0=1\)而非“未定义的操作”:离散、计数问题大都如此,可以参考讨论。然后就是很显然的卷积。

#include <bits/stdc++.h>
#define ll long long 
using namespace std;

const int N=4e5+10;
const int mod=998244353;

inline int qpow(ll x,ll y) {
    int c=1;
    for(; y; y>>=1,x=x*x%mod) if(y&1) c=x*c%mod;
    return c;
}
int p,pl,rev[N];
inline void ntt_init(int sum) {
    for(p=1,pl=0; p<sum;) p<<=1,pl++;
    for(int i=0; i<p; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(pl-1));
}
inline void ntt(int*a,int tp) {
    for(int i=0; i<p; ++i) if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int m=1; m<p; m<<=1) {
        ll wm=qpow(3,(mod-1)/(m<<1)); if(tp<0) wm=qpow(wm,mod-2);
        for(int i=0; i<p; i+=(m<<1)) { ll w=1,tmp;
            for(int j=0; j<m; ++j,w=w*wm%mod) {
                tmp=w*a[i+j+m]%mod;
                a[i+j+m]=(a[i+j]-tmp+mod)%mod;
                a[i+j]=(a[i+j]+tmp)%mod;
            }
        }
    }
    if(tp<0) {
        ll tmp=qpow(p,mod-2);
        for(int i=0; i<p; ++i) a[i]=tmp*a[i]%mod;
    }
}
int n,f[N],g[N];
ll fc[N],fv[N];

int main() {
    scanf("%d",&n);
    
		    

fc[0]=fc[1]=fv[0]=fv[1]=1; for(int i=2; i<=n; ++i) fv[i]=fv[mod%i]*(mod-mod/i)%mod; for(int i=2; i<=n; ++i) fv[i]=fv[i-1]*fv[i]%mod,fc[i]=fc[i-1]*i%mod; f[0]=1,f[1]=mod-1,g[0]=1,g[1]=n+1; for(int i=2; i<=n; ++i) { f[i]=fv[i]*((i&1)?mod-1:1)%mod; g[i]=fv[i]*((qpow(i,n+1)-1+mod)%mod)%mod*qpow(i-1,mod-2)%mod; } //for(int i=0; i<=n; ++i) printf("%d ",f[i]); printf("\n"); //for(int i=0; i<=n; ++i) printf("%d ",g[i]); printf("\n"); ntt_init(n+n+2); ntt(f,1); ntt(g,1); //for(int i=0; i<p; ++i) printf("%d ",f[i]); printf("\n"); //for(int i=0; i<p; ++i) printf("%d ",g[i]); printf("\n"); for(int i=0; i<p; ++i) f[i]=1LL*f[i]*g[i]%mod; ntt(f,-1); ll P=1,sum=0; for(int i=0; i<=n; ++i) { sum=(sum+P*fc[i]%mod*f[i]%mod)%mod; P=P*2%mod; } printf("%lld\n",sum); return 0; }

写代码是别把p和mod弄混了……


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C++ day01 C++综述、教材、推荐阅.. 下一篇[SDOI2019] 热闹又尴尬的聚会

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }