P14461 【MX-S10-T2】『FeOI-4』青年晚报题解

思路分析：

首先整理式子得出：

f_{i,j}=f_{i-2,j}+(j+1)\times(j+2)\times f_{i-2,j+2}

g

的递推式与之相同。那么

f_{0,j}

可以直接递推推到的就是偶数的

n

。对于奇数，推到

n-1

，再暴力做一次即可。接下来只考虑偶数时

f

如何求解。

观察数据范围不难发现正解应该是

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;
}

完结撒花！！！

P14461 【MX-S10-T2】『FeOI-4』青年晚报题解

文章操作

思路分析：

AC Code:

相关推荐

评论

P14461 【MX-S10-T2】『FeOI-4』青年晚报题解