ZOJ 3899 State Reversing【NTT】

逃离我推掉我的手 2022-08-05 11:25 102阅读 0赞

题意：  
有N（有序号）个怪兽，给出M（1～M）个房间，每个房间的初始状态为1，接下来有D次操作，每次操作是选择一个区间使得区间内房间的状态反转（0->1 , 1->0），每次操作后计算将这N个怪兽放进所有状态为1的房间内，且每个状态为1的房间非空的方案数。（注意房间之间不可辨别。两种方案一样，当且仅当两种方案中存在两个房间，里面的怪兽数量以及编号一致）

思路：  
用线段树来更新available的房间数目，发现方案数和整数拆分相同，即第二类斯特林数，但是第二类斯特林数是O(n2)的递推，因此核心问题是如何在O(nlogn)的时间复杂度内算出第二类斯特林数。  
核心问题思路：  
观察到n是不变的，k在变动，令F\[i\]为n个东西放i个盒子的方案数  
那么可以这么计算：

F\[i\]=1i!∑k=0i(−1)kCki∗(i−k)n

然后转化一下：

F\[i\]=∑k=0i(−1)k(i−k)nk!(i−k)!

F\[i\]=∑k=0i(−1)kk!×(i−k)n(i−k)!

以此可见FFT的卷积，在  (nlogn) 内预处理出，可得到答案。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    #define debug(a) cout << #a" = " << (a) << endl;
    #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define getidx(l,r) (l+r|l!=r)
    #define ls getidx(l,mid)
    #define rs getidx(mid+1,r)
    #define lson l,mid
    #define rson mid+1,r
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=300005;
    const int MOD=880803841;
    
    ll qpow(ll a,ll b,ll p)
    {
        ll base=a,res=1;
        while(b)
        {
            if(b&1) res=res*base%p;
            base=base*base%p;
            b>>=1;
        }
        return res;
    }
    
    namespace NTT
    {
    const int r=26,gl=25;
    ll p,rp[50],irp[50];
    void setMOD(ll _p=880803841)
    {
        p=_p;
        for(int i=0; i<gl; i++) rp[i]=qpow(r,(p-1)/(1<<i),p);
    }
    void FFT(ll a[],int n,ll wt[]=rp)
    {
        for(int i=0,j=0; i<n; i++)
        {
            if(j>i) swap(a[i],a[j]);
            int k=n;
            while(j&(k>>=1)) j&=~k;
            j|=k;
        }
        for(int m=1,b=1; m<n; m<<=1,b++)
            for(int k=0,w=1; k<m; k++)
            {
                for(int i=k; i<n; i+=m<<1)
                {
                    int v=a[i+m]*w%p;
                    if((a[i+m]=a[i]-v)<0) a[i+m]+=p;
                    if((a[i]+=v)>=p) a[i]-=p;
                }
                w=w*wt[b]%p;
            }
    }
    void IFFT(ll a[], int n)
    {
        for(int i=0; i<gl; i++) irp[i]=qpow(rp[i],n-1,p);
        FFT(a,n,irp);
        ll inv=qpow(n,p-2,p);
        for(int i=0; i<n; i++) a[i]=a[i]*inv%p;
    }
    void Mul(ll a[],ll b[],ll n,ll c[])
    {
        FFT(a,n);
        FFT(b,n);
        for(int i=0; i<n; i++) c[i]=a[i]*b[i]%p;
        IFFT(c,n);
    }
    }
    
    ll a[MAXN],b[MAXN],c[MAXN];
    int sum[200005],lazy[200005];
    
    void pushup(int l,int r)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        sum[idx]=sum[ls]+sum[rs];
    }
    
    void pushdown(int l, int r)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        if(lazy[idx])
        {
            sum[ls]=(mid-l+1)-sum[ls];
            sum[rs]=(r-mid)-sum[rs];
            lazy[ls]^=1;
            lazy[rs]^=1;
            lazy[idx]=0;
        }
    }
    
    void build(int l,int r)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        lazy[idx]=0;
        if(l==r)
        {
            sum[idx]=1;
            return;
        }
        build(lson);
        build(rson);
        pushup(l,r);
    }
    
    void update(int l,int r,int L,int R)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        if(L<=l && r<=R)
        {
            sum[idx]=(r-l+1)-sum[idx];
            lazy[idx]^=1;
            return;
        }
        pushdown(l,r);
        if(L<=mid) update(lson,L,R);
        if(R>mid) update(rson,L,R);
        pushup(l,r);
    }
    
    int main()
    {
        int T;
        read(T);
        while(T--)
        {
            int N,m,D;
            scanf("%d%d%d",&N,&m,&D);
    
            CLR(a,0);CLR(b,0);
            int n=1;
            while(N>=n) n<<=1;
            a[0]=1;
    
            for(int i=1; i<=N; i++)  a[i]=a[i-1]*i%MOD;
            for(int i=0; i<=N; i++)  a[i]=b[i]=qpow(a[i],MOD-2,MOD);
            for(int i=1; i<=N; i+=2) a[i]=a[i]*(MOD-1)%MOD;
            for(int i=0; i<=N; i++)  b[i]=b[i]*qpow(i,N,MOD)%MOD;
    
            n=n*2;
    
            NTT::setMOD();
            NTT::Mul(a,b,n,c);
    
            build(1,N);
            while(D--)
            {
                int L,R;
                scanf("%d%d",&L,&R);
                update(1,N,L,R);
                int t=sum[getidx(1,N)];
                printf("%lld\n",c[t]);
            }
        }
        return 0;
    }