Description

今年多校第一场的题哦

传送门

Analysis

看到积分非常傻眼,而且题目里还声称“答案是有理数”,这自然引起我们的好奇。注意到分子分母其实是齐次的,所以多半是什么东西消掉了才这样的吧x

上下都是 \(4N,2N\) ,不妨只考虑一个 \(N\),然后菜鸡的分析只会大暴力,最暴力的想法就是,呃,先换元试试看。\(x=\frac{1}{\tau}\) 代换后

\[ \int_0^{+\infty}\frac{\tau^{-N-1}}{e^{\frac1\tau}-1}\mathrm{d}\tau= \int_0^{+\infty}\frac{x^{N-1}}{e^x-1}\mathrm{d}x \]

这么个形式看上去就很……咳咳,很特殊函数吧(

对,它就是 \(\text{Riemann-}\zeta\) 的定义之一:

\[ {\displaystyle \zeta (s)={\frac {1}{\Gamma (s)}}\int _{0}^{\infty }{\frac {x^{s-1}}{e^{x}-1}}\,\mathrm {d} x\quad {\text{for}}\quad \operatorname {Re} (s)\equiv \sigma >1,} \]

所以我们就顺理成章地只需要求

\[ \frac{\zeta(4N)(4N-1)!}{\zeta^2(2N)(2N-1)!^2} \]

\(\text{Riemann-}\zeta\) 函数和多项式自然数点值的求和有关,并且偶数函数值都是已知的,作为精通特殊函数论的殿堂级离散数学家的你一定知道这个性质

\[ \zeta(2n) = \frac{(-1)^{n+1}B_{2n}(2\pi)^{2n}}{2(2n)!} \]

代入化简,最后居然得到这么简单的柿子

\[ -\frac{2NB_{4N}}{B_{2N}^2} \]

好像就没啥了……预处理完伯努利数就能做。

虽然说得轻巧,但这也不失为一次引入特殊函数的大胆尝试,咱也算是见识前沿东西了(bushi

Implementation

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// 静かな海
#include <bits/stdc++.h>
#define dbg(x, y...) fprintf(stderr, x, y)
#define pline() (dbg("Passing Line #%d in Func [%s]", __LINE__, __FUNCTION__))
using namespace std;

const int N=1.2e6+3,P=1e9+9;
const double PI=acos(-1);
struct C{
double x,y;
C operator+(C a)const{return{x+a.x,y+a.y};}
C operator-(C a)const{return{x-a.x,y-a.y};}
C operator*(C a)const{return{x*a.x-y*a.y,x*a.y+y*a.x};}
}a[N],b[N],c[N],d[N],w[N];
int n,r[N],x[N],y[N],z[N];
int qp(int a,int b){
int r=1;
for(;b;b>>=1,a=a*1ll*a%P)if(b&1)r=r*1ll*a%P;
return r;
}
void fft(C*a,bool b=0){
int i,j,k;
C *g,*u,*v,x;
for(i=0;i<n;++i)if(i<r[i])swap(a[i],a[r[i]]);
for(i=1;i<n;i*=2)for(j=0;j<n;j+=i*2)for(k=0,g=w+i,u=a+j,v=u+i;k<i;++k)
x=g[k]*v[k],v[k]=u[k]-x,u[k]=u[k]+x;
if(b)for(i=0,reverse(a+1,a+n);i<n;++i)a[i].x/=n,a[i].y/=n;
}
void pre(int m){
int i,j;
for(n=1;n<m;n*=2);
for(i=1,w[j=n>>1]={1,0};i<n;++i)r[i]=(r[i>>1]>>1)|((i&1)?j:0);
for(i=j+1;i<n;++i)w[i]={cos(2*(i-j)*PI/n),sin(2*(i-j)*PI/n)};
for(i=j-1;i;--i)w[i]=w[i*2];
}
#define to(_) ((long long)((_)+.5)%P)
void inv(int m){
if(m==1){y[0]=qp(x[0],P-2),pre(2);return;}
int i,j,l=m+1>>1;
inv(l);
for(i=0;i<l;++i)a[i]={y[i]>>15,y[i]&32767};
for(i=l;i<n;++i)a[i]={0,0};
fft(a);
for(i=0;i<n;++i)j=i?n-i:0,c[i]=C{.5*(a[i].x+a[j].x),.5*(a[i].y-a[j].y)}*a[i],d[i]=C{.5*(a[i].y+a[j].y),.5*(a[j].x-a[i].x)}*a[i];
fft(c,1),fft(d,1);
for(i=0;i<n;++i)z[i]=((to(c[i].x)<<30)+(to(c[i].y+d[i].x)<<15)+to(d[i].y))%P;
pre(m*2);
for(i=0;i<m;++i)a[i]={x[i]>>15,x[i]&32767};
for(i=m;i<n;++i)a[i]={0,0};
for(i=0;i<n;++i)b[i]={z[i]>>15,z[i]&32767};
fft(a),fft(b);
for(i=0;i<n;++i)j=i?n-i:0,c[i]=C{.5*(a[i].x+a[j].x),.5*(a[i].y-a[j].y)}*b[i],d[i]=C{.5*(a[i].y+a[j].y),.5*(a[j].x-a[i].x)}*b[i];
fft(c,1),fft(d,1);
for(i=0;i<n;++i)z[i]=((to(c[i].x)<<30)+(to(c[i].y+d[i].x)<<15)+to(d[i].y))%P;
for(i=0;i<m;++i)y[i]=(y[i]=(y[i]*2-z[i])%P)<0?y[i]+P:y[i];
}
int fac[N], ifac[N];
int main(){
int n=4.1e5,m,i,j;
fac[0] = ifac[0] = 1;
for (i=1; i<=n; i++) fac[i]=1ll*fac[i-1]*i%P;
ifac[n] = qp(fac[n], P-2);
for (i=n-1; i; i--) ifac[i]=1ll*ifac[i+1]*(i+1)%P;
for (i=0; i<n; i++) x[i]=ifac[i+1];
inv(n);
for(i=0; i<n; i++) y[i]=1ll*y[i]*fac[i]%P;
scanf("%d", &m);
while(m--)
{
scanf("%d", &n);
j=0;
j = qp(y[2*n], P-2);
j = 1ll * j * j % P;
j = 2ll * n * y[4*n] % P * j % P;
j = (P - j) % P;
printf("%d\n", j);
}
return 0;
}