CF997C Sky Full of Stars

不念不忘少年蓝@ 2021-12-23 15:09 120阅读 0赞

[CF997C Sky Full of Stars][]

计数好题

[在Ta的博客查看][Ta]

容斥式子：发现只要每个钦定方案的贡献都考虑到再配上容斥系数就是对的

O(n^2)->O(n)

把麻烦的i=0，j=0特殊考虑下

剩下的，先把麻烦的东西化简干净

然后枚举一维i，剩下的二项式定理！！！！

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    #define pb push_back
    #define solid const auto &
    #define enter cout<<endl
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    
    namespace Miracle{
    const int N=1e6+5;
    const int mod=998244353;
    int ad(int x,int y){
        return (x+y)>=mod?x+y-mod:x+y;
    }
    int qm(int x,ll y){
        int ret=1;
        while(y){
            if(y&1) ret=(ll)ret*x%mod;x=(ll)x*x%mod;y>>=1;
        }return ret;
    }
    int inv[N],jie[N];
    int C(int n,int m){
        if(n<0||m<0||n<m) return 0;
        return (ll)jie[n]*inv[m]%mod*inv[n-m]%mod;
    }
    int main(){
        int n;rd(n);
        ll ans=0;
        jie[0]=1;
        for(reg i=1;i<=n;++i) jie[i]=(ll)jie[i-1]*i%mod;
        inv[n]=qm(jie[n],mod-2);
        for(reg i=n-1;i>=0;--i) inv[i]=(ll)inv[i+1]*(i+1)%mod;
        for(reg i=1;i<=n;++i){
            ans=ad(ans,(i+1)&1?mod-(ll)C(n,i)*qm(3,(ll)n*(n-i)+i)%mod:(ll)C(n,i)*qm(3,(ll)n*(n-i)+i)%mod);
        }
        ans=ans*2%mod;
        ll sum=0;
        ll base=1;
        for(reg i=0;i<=n-1;++i){
            sum=ad(sum,(i+1)&1?mod-(ll)C(n,i)*ad(qm(ad(1,mod-base),n),mod-qm(mod-base,n))%mod:(ll)C(n,i)*ad(qm(ad(1,mod-base),n),mod-qm(mod-base,n))%mod);
            base=base*3%mod;
        }
        ans=(ans+sum*3)%mod;
        ot(ans);
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

转载于:https://www.cnblogs.com/Miracevin/p/10787359.html

[CF997C Sky Full of Stars]: https://www.luogu.org/problemnew/show/CF997C
[Ta]: https://www.luogu.org/blog/wcx/solution-cf997c