10.15T1 容斥原理+二项式定理优化

这题其实一眼就知道肯定要容斥了，分为行列单独容斥，最后交叉 的时候容斥一下就有70分了（暴力容斥）

70分题解：

code：

#include<iostream>
#include<cstdio>
#define N 5000006
using namespace std;
const long long mod=998244353;
long long n,k;
long long jie[N],ci[N],c[3001][3001];
void pre() {
    ci[0]=1;
    for(int i=1; i<=n*n; i++)ci[i]=ci[i-1]*k%mod;
    for (int i=0; i<=n; i++)
        for (int j=0; j<=i; j++)
            if (j==0||i==j) c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
int main() {
//    freopen("magic.in","r",stdin);
//    freopen("magic.out","w",stdout);
    cin>>n>>k;
    pre();
    long long ans=0;
    for(long long i=1; i<=n; i++) {
        if(i&1) {
            ans+=((ci[(n-i)*n]*c[n][i])%mod*ci[i])%mod;
            ans+=mod;
            ans%=mod;
        } else {
            ans-=((ci[(n-i)*n]*c[n][i])%mod*ci[i])%mod;
            ans+=mod;
            ans%=mod;
        }
    }
    ans*=2;
    for(long long i=1; i<=n; i++) {
        for(long long j=1; j<=n; j++) {
            if((i+j)&1) {
                ans+=(ci[((n-(i+j))*n)+i*j]*c[n][i])%mod*c[n][j]%mod*k%mod;
                ans%=mod;
            } else {
                ans-=(ci[((n-(i+j))*n)+i*j]*c[n][i])%mod*c[n][j]%mod*k%mod;
                ans=(ans+mod)%mod;
            }
        }
    }
    cout<<ans;
    return 0;
}

100分：

官方code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<ctime>
#define MAXN 200005
#define ll long long
#define maxn 15
#define maxs 1000005
#define inf 1e9
#define eps 1e-9
using namespace std;
inline char gc() {
    static char now[1<<16],*S,*T;
    if (T==S) {
        T=(S=now)+fread(now,1,1<<16,stdin);
        if (T==S) return EOF;
    }
    return *S++;
}
inline ll readlong() {
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x*=10;
        x+=ch-'0';
        ch=getchar();
    }
    return x*f;
}
const int N=1000005;
const int mod=998244353;
ll res,ans,n,k;
ll fac[N],inv[N];
void update(ll &x,ll y) {
    x+=y;
    if(x<0) {
        x+=mod;
    }
    if(x>=mod) {
        x-=mod;
    }
}
ll ksm(ll x,ll k) {
    update(x,0);
    ll ret=1;
    ll ans=x;
    while(k) {
        if(k&1) {
            ret=ret*ans%mod;
        }
        ans=ans*ans%mod;
        k>>=1;
    }
    return ret;
}
ll calc(ll x,ll y) {
    if(x<y) {
        return 0;
    }
    if(x==y) {
        return 1;
    }
    return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main() {
    freopen("magic.in","r",stdin);
    freopen("magic.out","w",stdout);
    n=readlong();
    k=readlong();
    fac[0]=1;
    for(int i=1; i<=n; i++)fac[i]=fac[i-1]*i%mod;
    inv[n]=ksm(fac[n],mod-2);
    for(int i=n-1; i>=0; i--)inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=1; i<=n; i++) {
        int a=1ll*calc(n,i)*ksm(-1,i+1)%mod;
        int x=ksm(k,(1ll*n*(n-i)+i)%(mod-1));
        update(ans,1ll*a*x%mod);
    }
    ans=2*ans%mod;
    for(int i=0; i<n; i++) {
        int tmp=mod-ksm(k,i);
        int x=(ksm(tmp+1,n)+mod-ksm(tmp,n))%mod;
        int a=1ll*calc(n,i)*ksm(-1,i+1)%mod;
        update(res,1ll*a*x%mod);
    }
    res=k*res%mod;
    printf("%lld
",(ans+res)%mod);
    return 0;
}

本人code：

#include<iostream>
#include<cstdio>
#define N 1000005
using namespace std;
const long long mod=998244353;
long long n,k;
long long jie[N],inv[N];
long long ksm(long long a,long long b) {
    long long ans=1;
    for(; b; b>>=1) {
        if(b&1) {
            ans*=a;
            ans%=mod;
        }
        a*=a;
        a%=mod;
    }
    return ans;
}
long long read() {
    long long x=0,f=1;
    char c=getchar();
    while(!isdigit(c)) {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)) {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
long long C(long long a,long long b) {
    return (((jie[a]*inv[b])%mod*inv[a-b])%mod+mod)%mod;
}
void pre() {
    jie[0]=1;
    for(long long i=1; i<=n; i++)jie[i]=jie[i-1]*i%mod;
    inv[n]=ksm(jie[n],mod-2);
    for(long long i=n-1; i>=0; i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int main() {
    n=read(),k=read();
    pre();
    long long ans=0;
    for(long long i=1; i<=n; i++) {
        if(i&1) {
            ans+=C(n,i)*ksm(k,(n-i)*n)%mod*ksm(k,i);
            ans+=mod;
            ans%=mod;
        } else {
            ans-=C(n,i)*ksm(k,(n-i)*n)%mod*ksm(k,i);
            ans+=mod;
            ans%=mod;
        }
    }
    ans*=2;
    ans%=mod;
    for(long long i=0; i<n; i++) {
        if(i&1) {
            long long temp1=C(n,i);
            long long temp2=(1-ksm(k,i)+2*mod)%mod;
            long long temp3=ksm(k,i);
            temp2=ksm(temp2,n);
            temp3=ksm(temp3,n);
            if(n&1){
                temp3=-temp3;
            }
            ans+=k*(temp1*(temp2-temp3)%mod+mod)%mod;
            ans+=mod;
            ans%=mod;
        } else {
            long long temp1=C(n,i);
            long long temp2=(1-ksm(k,i)+2*mod)%mod;
            long long temp3=ksm(k,i);
            temp2=ksm(temp2,n);
            temp3=ksm(temp3,n);
            if(n&1){
                temp3=-temp3;
            }
            ans-=k*(temp1*(temp2-temp3)%mod+mod)%mod;
            ans+=mod;
            ans%=mod; 
        }
    }
    cout<<ans;
    return 0;
}

over