AT_aising2020_f Two Snuke
题意：对于一个十元组 \((a_1,a_2,b_1,b_2,c_1,c_2,d_1,d_2,e_1,e_2)\) ，定义它合法当且仅当满足下列条件：
-
\(0\le a_1<a_2\)
-
\(0\le b_1<b_2\)
-
\(0\le c_1<c_2\)
-
\(0\le d_1<d_2\)
-
\(0\le e_1<e_2\)
-
\(a_1+a_2+b_1+b_2+c_1+c_2+d_1,d_2+e_1+e_2\le n\)
现在有 \(T\) 组数据，每次对于给定的 \(n\) 求所有合法十元组 \((a_2-a_1)(b_2-b_1)(c_2-c_1)(d_2-d_1)(e_2-e_1)\) 之和对 \(10^9+7\) 取模的结果。
\(1\le T\le 100,1\le n\le 10^9\)
\(sol\)：首先考虑两两分组，我们定义\(a_1+a_2=n_1,a_2-a_1=m_1\dots e_1+e_2=n_5,e_2-e_1=m_5\) \(DP\) 我们令 \(f_{i,j}\) 表示前 \(i\) 组数和为 \(j\) 的所有合法情况的 \(\prod\limits_{k=1}^i m=1\) 的和，最终答案就是 \(\sum\limits_{i=1}^n f_{5,i}\)。
现在我们考虑一组数和为 \(n_i\)
可以分成 \(0\) 和 \(n_i\) 此时 \(m_i\) 为 \(n_i\)
也可以分成 \(1\) 和 \(n_i-1\) ，此时 \(m_i\) 为 \(n_i-2\)
以此类推，我们可以得到一组数 \(n_i\) 确定时所有情况的 \(m_i\) 呈现等差数列的形式，我们设 \(g_i\) 为一组数和为 \(i\) 时所有情况 \(m\) 的和。需要分两种情况，如果 \(i\) 为奇数，\(g_i=\frac{(i+1)^2}{4}\) ，\(i\) 为偶数时 \(g_i=\frac{k(k+2)}{4}\) 。
然后我们就可以得到一个状态转移式 \(f_{i,j}=\sum\limits_{i=0}^j f_{i-1,j-k}\times g_k\) ，可以观察到如果把 \(f_{i-1}\) 和\(g\) 看作生成函数的话，这个转移就是让 \(f_i\) 等于它们的卷积，并且很显然 \(f_1\) 和 \(g\) 是等价的，所以 \(f_5\) 就相当于 \(g^5\) ，最后答案就是这个生成函数的前缀和。我们可以求出 \(g\) 的封闭形式 \(\frac{x}{(1-x)^2(1-x^2)}\) 所以 \(g^5\) 是 \(\frac{x^5}{(1-x)^{10}(1-x^2)^{5}}\) 。因为要求前缀和所以再乘上 \(\frac1{1-x}\) 最终生成函数卷积出的形式就是 \(\frac{x^5}{(1-x)^{11}(1-x^2)^{5}}\) （有一篇题解似乎也得到了类似的形式，但我没看懂推导过程），\(x^5\) 相当于平移 \(5\) 位比较简单先不管。而 \(\frac1{(1-x)^{11}(1-x^2)^{5}}\) 这玩意第 \(n\) 项系数就是 \(\sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor} {k+4\choose4}\times{n-2k+10\choose 10}\) 现在 \(n\) 给定了，\(\sum\) 后面那坨就是关于 \(k\) 的 \(14\) 次函数，求前缀和就是 \(15\) 次函数，直接拉格朗日插值求前 \(\lfloor\frac{n}{2}\rfloor\) 项的和就做完了。
复杂度 \(O(16^2T)\) ，其实可以做到 \(O(16T)\) 但 \(T\) 不是很大所以没什么影响。
一个小问题：
为什么不能直接对 \(f_5\) 做拉插，这里我之前也没想通。其实是因为 \(g\) 要分奇偶所以不是二次函数，而是\(g_i=\frac{(i+1)^2\times((-1)^{i+1}+1)}{4}+\frac{k(k+2)\times((-1)^i+1)}{4}\) 这样指数函数乘二次函数的形式，所以最后卷积出的 \(f_5\) 不是多项式做不了拉插。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll fac[100]={1},sum[100],n=50;
inline ll rd()
{
char c;ll f=1;
while(!isdigit(c=getchar()))if(c=='-')f=-1;
ll x=c-'0';
while(isdigit(c=getchar()))x=x*10+(c^48);
return x*f;
}
inline ll qp(ll x,ll y)
{
ll res=1;
while(y)
{
if(y&1) (res*=x)%=mod;
(x*=x)%=mod,y>>=1;
}
return res;
}
ll C(ll n,ll m)
{
ll s=1;
for(int i=1;i<=m;i++) (s*=(n-i+1))%=mod;
return s*qp(fac[m],mod-2)%mod;
}
ll ans(ll k)
{
if(k<5) return 0;k-=5;
n=min(50ll,k/2);
for(int j=0;j<=n;j++)
sum[j]=C(j+4,4)*C(k-2*j+10,10)%mod;
k/=2;ll s=0;
for(int j=1;j<=n;j++) (sum[j]+=sum[j-1])%=mod;
if(k<=n) return (sum[k]+mod)%mod;
for(int i=0;i<=n;i++)
{
ll s1=sum[i],s2=1;
for(int j=0;j<=n;j++) if(j!=i)
s1=s1*(k-j)%mod,s2=s2*(i-j)%mod;
(s+=s1*qp(s2,mod-2)%mod)%=mod;
}
return (s+mod)%mod;
}
int main()
{
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
for(ll t=rd();t--;) printf("%lld\n",ans(rd()));
return 0;
}