题目概述

在 $n\times n$ 的棋盘上放 $n$ 个车(ju)，使得车之间不会吃到，且在不经过车的情况下能够从 $(1,1)$ 走到 $(n,n)$ ，求方案数。

解题报告

能走到只需要满足没有对角线被拦住，写下答案式子：

$$ \begin{aligned} &=n!+1-2\sum_{i=0}^{n-1}i!+\sum_{i=1}^{n-1}\sum_{j=1}^{n-i}(n-i-j)!\\ &=n!+1-2\sum_{i=0}^{n-1}i!+\sum_{i=1}^{n-1}(n-1-i)!i\\ &=n!+1-2\sum_{i=0}^{n-1}i!+\sum_{i=2}^{n}(n-i)!(i-1)\\ &=n!+1-3\sum_{i=0}^{n-1}i!+n\sum_{i=0}^{n-2}i!\\ \end{aligned} $$

刚开始写丑了，要存三个量，继续化简就发现只需要两个量。等等…… $n\le 10^9$ ？黑科技分段打表大法。

然后BZOJ过不了，反正校内OJ过了，不想管了。

示例程序

打表

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int BA=88,MOD=1e9+7,S=222223;

int fac=1,sum=1;char ID[BA];
int len;char s[10000000];

inline void Add(int x){
    int now[10];memset(now,0,sizeof(now));now[0]=0;do now[++now[0]]=x%BA,x/=BA; while(x);
    for (int i=5;i;i--) s[++len]=ID[now[i]];
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
int main(){
    freopen("table.out","w",stdout);
    for (int i=0,now=32;i<BA;i++,now++) {if (now==34) now++;if (now==47) now++;if (now==92) now++;ID[i]=now;}
    fac=1;sum=1;
    for (int i=1;i<=1000000000;i++){
        fac=(LL)fac*i%MOD;AMOD(sum,fac);if (i%S==1) Add(fac),Add(sum);
        // int ans=0,A=(LL)fac*Pow(i,MOD-2)%MOD;
        // AMOD(ans=fac,2);AMOD(ans,MOD-(LL)3*(sum+MOD-fac)%MOD);AMOD(ans,((LL)sum+MOD-fac+MOD-A)*i%MOD);
        // printf("%d\n",ans);
    }
    return printf("%s\n",s+1),0;
}

主程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int BA=88,MOD=1e9+7,S=222223,maxs=4500;
const char* s="balabala"; //这个是上面打出来的表
    
int te,n,ID[256],A[maxs+5],B[maxs+5];

inline void Make(){
    for (int i=0,now=32;i<BA;i++,now++) {if (now==34) now++;if (now==47) now++;if (now==92) now++;ID[now]=i;}
    for (int i=1,S=0;i<=maxs;i++,S+=10){
        for (int j=0;j<5;j++) A[i]=A[i]*BA+ID[s[S+j]];
        for (int j=5;j<10;j++) B[i]=B[i]*BA+ID[s[S+j]];
    }
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (Make(),scanf("%d",&te);te;te--){
        scanf("%d",&n);if (n<=2) {puts("0");continue;}int pos=(n-1)/S,fac=A[pos+1],sum=B[pos+1];
        for (int i=pos*S+2;i<=n;i++) fac=(LL)fac*i%MOD,AMOD(sum,fac);
        int ans=0,lst=(LL)fac*Pow(n,MOD-2)%MOD;
        AMOD(ans=fac,2);AMOD(ans,MOD-(LL)3*(sum+MOD-fac)%MOD);
        AMOD(ans,((LL)sum+MOD-fac+MOD-lst)*n%MOD);printf("%d\n",ans);
    }
    return 0;
}