[分块打表] HHHOJ#292. 「湖南省队集训2018 Day2」游戏

稍微画几下,可以发现,不可达的情况必定存在左上到右下的斜线。

然后就可以算方案数了,注意要减去有两条斜线的情况。

式子是 \[ n!-1-2\sum_{i=1}^{n-1} (n-i)!+\sum_{i=2}^n (n-i)!(i-1) \] 先化简,可以得到 \[ n!-1+n\sum_{i=0}^{n-2}i!-3\sum_{i=1}^{n-1}i! \] 分块打表即可。

化简要多化几步,直到尽量好算为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<algorithm>
#include<cstring>
const char preS[]="..." \\ 表略
using namespace std;
typedef long long LL;
const int maxn=100005,P=1e9+7;
int n,m,S,fac[4005],sum[4005],ans;
int getVal(char ch){
if(ch==38) ch='?'; if(ch==39) ch='\\';
return ch-40;
}
int Sget(int p){
int res=0;
for(int i=p;i>=p-4;i--){
res=res*80+getVal(preS[i]);
}
return res;
}
int _test;
LL Pow(LL a,LL b){
LL res=1;
for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;
return res;
}
int main(){
S=250000;
fac[0]=1; sum[0]=0;
for(int i=1;i<=4000;i++){
fac[i]=Sget(i*10-5); sum[i]=Sget(i*10);
}
scanf("%d",&_test);
while(_test--){
scanf("%d",&n);
if(n<=2){ puts("0"); continue; }
LL _fac=fac[n/S],_sum=sum[n/S];
for(int i=n/S*S+1;i<=n;i++) _fac=_fac*i%P, _sum=(_sum+_fac)%P;
LL fac1=_fac*Pow(n,P-2)%P;
ans=_fac-1+(LL)n*((1+_sum-_fac-fac1)%P)%P-(_sum-_fac)*3%P;
printf("%d\n",(ans%P+P)%P);
}
return 0;
}