P14461 【MX-S10-T2】『FeOI-4』青年晚报 题解
Planetary_system
·
·
题解
思路分析：
首先整理式子得出：
f_{i,j}=f_{i-2,j}+(j+1)\times(j+2)\times f_{i-2,j+2}
观察数据范围不难发现正解应该是 $O(m^2)$ 的做法，考虑计算 $f_{0,k}$ 对 $f_{n/n-1,j}$ 的贡献:
- 首先有当 $j=m/m-1$ 时，$f_{i,j}$ 始终为 $f_{0,j}$。
- 对于左边的，$j$ 的系数为 $1$，$j+2$ 的系数为 $-\frac n2(j+1)(j+2)$，$j+4$ 的系数为 $\frac n2\frac{\frac n2-1}2(j+1)(j+2)(j+3)(j+4)$……。
- 整理发现每次对系数做如下修改：
- 修改正负号（即 $\times-1$）。
- 增加递推系数（即 $\times k(k-1)$）。
- 修改贡献次数（即 $\times \frac{n-k+j+2}{k-j}$）。
于是我们找到了这题的规律！
## AC Code:
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5010,mod=1e9+7;
int inv[N],f[N],g[N],F[N],G[N];
int qpow(int x,int y){
int res=1;
while(y){
if(y&1)res=res*x%mod;
x=x*x%mod,y>>=1;
}return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++)inv[i]=qpow(i,mod-2);
for(int i=0;i<=m;i++)cin>>F[i];
for(int i=0;i<=m;i++)cin>>G[i];
for(int i=m;i>=0;i--)
for(int j=i,k=0,p=1,q=1;j<=m;)
f[i]+=p*q%mod*F[j]%mod,f[i]%=mod,
g[i]+=p*q%mod*G[j]%mod,g[i]%=mod,
j+=2,p=(mod-j)*(j-1)%mod*p%mod,
k++,q=(n/2-k+1)*inv[k]%mod*q%mod;
for(int i=0;i<=m;i++)
cout<<(n&1?(g[i]+(i+1)*g[i+1]%mod+mod)%mod:f[i])<<" \n"[i==m];
for(int i=0;i<=m;i++)
cout<<(n&1?(f[i]-(i+1)*f[i+1]%mod+mod)%mod:g[i])<<" \n"[i==m];
return 0;
}
```
完结撒花！！！