题解：P13234 [GCJ 2015 Finals] Campinatorics

小清新数数题，像是二维错排。

3

的限制是很好处理的，放置

k

个

3

相当于去除

k

行

k

列，问题规模缩小至

(n-k)\times (n-k)

。

考虑只有

1,2

怎么做，设答案为

f_n

。

一个平凡的想法是从

f_{n-1}

转移而来。我们钦定第

n

行的第

n

个数为

1

，然后枚举第

n

行

2

的位置

i

，然后将原本第

i

列的

2

放置到第

n

列，这样我们就实现了一个

f_{n-1}\rightarrow f_n

的映射，即

f_n=n\times (n-1)\times f_{n-1}

乘的

n

是把钦定的最后一行放回到任意一行中。

然而这样存在漏数的情况。类比错拍的递推，上式默认了去掉特定的一行一列（第

n

列有

1

的行，该行有

2

的列）后的矩阵依然合法，而则不总是存在。

考虑计算不存在的情况。容易发现，不存在当且仅当该特定的行列处于一个合法的

2\times 2

矩阵中（这也和错排类似），这一部分的贡献是

n\times (n-1)^2\times f_{n-2}

。

最后再处理

3

的影响即可。

时间复杂度

O(Tn)

。

CPP

#include<bits/stdc++.h>
#define il inline
using namespace std;
const int N=1000000;
const int maxn=1000010;
const int mod=1e9+7;
il int read(){
    int x=0;
    char c=getchar();
    for(;!(c>='0'&&c<='9');c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
il int fpow(int n,int m,int x=1){
    for(;m;m>>=1,n=1ll*n*n%mod)
        if(m&1) x=1ll*x*n%mod;
    return x;
}
int fac[maxn],ifac[maxn];
int f[maxn],T,n,X,ans;
int C(int i){return (1ll*i*(i-1)/2)%mod;}
int main(){
    fac[0]=ifac[0]=1;
    for(int i=1;i<=N;i++) 
        fac[i]=1ll*fac[i-1]*i%mod;
    ifac[N]=fpow(fac[N],mod-2);
    for(int i=N-1;i;i--) 
        ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
    f[0]=1,f[1]=0,f[2]=2;
    for(int i=3;i<=N;i++){
        f[i]=1ll*f[i-1]*(i-1)%mod*i%mod;
        f[i]=(f[i]+1ll*f[i-2]*i%mod*(i-1)%mod*(i-1))%mod;
    }
    // for(int i=1;i<=10;i++)
    //     printf("%d ",f[i]);
    // printf("\n");
    T=read();
    for(int Case=1;Case<=T;Case++){
        n=read(),X=read(),ans=0;
        for(int i=1,tot=1;i<=n;i++){
            tot=1ll*tot*(n-i+1)%mod*(n-i+1)%mod;
            if(i>=X) ans=(ans+1ll*tot*f[n-i]%mod*ifac[i])%mod;
        }
        if(!X) ans=(ans+f[n])%mod;
        printf("Case #%d: %d\n",Case,ans);
    }
    return 0;
}

题解：P13234 [GCJ 2015 Finals] Campinatorics

文章操作

相关推荐

评论

题解：P13234 [GCJ 2015 Finals] Campinatorics