yukicoder No.554 recurrence formula

問題はこちら
No.554 recurrence formula - yukicoder

とする
このとき
よりとなりの漸化式が得られる
でありなので、これにより計算できる

long s[100100];
n,ans,m=1e9+7;
main(){
	scanf("%d",&n);
	if(n==1)ans=1;
	else{
		s[1]=1;
		for(int i=2;i<=n;i++)s[i]=(i*s[i-1]+s[i-2])%m;
		ans=(s[n]-s[n-2]+m)%m;
	}
	printf("%d",ans);
}

s[n]は三項間漸化式で得られ、a[n]はs[n]とs[n-2]で得られるので、これはs[n],s[n-1],s[n-2]の3状態のDPといえる
これをa[n],s[n-1],s[n-2]の3状態だと思えば、要するに「a[n]、n-1までの奇数項目の和、n-1までの偶数項目の和」ということ

long esum,osum,an;
n,m=1e9+7;
main(){
	scanf("%d",&n);
	an=1;
	for(int i=2;i<=n;i++){
		if(i%2==1){
			esum=(esum+an)%m;
			an=i*esum%m;
		}else{
			osum=(osum+an)%m;
			an=i*osum%m;
		}
	}
	printf("%d",an);
}

これをひとまず縮める

long t[2];
i,n,m=1e9+7;
main(a){
	scanf("%d",&n);
	for(i=2;i<=n;i++){
		t[i%2]=(t[i%2]+an)%m;
		a=t[i%2]*i%m;
	}
	printf("%d",a);
}

tは毎回剰余をとらなくても大丈夫。その場合でもt*iの計算は64bit整数の範囲に収まるので剰余は各回1回だけ取れば良い

long t[2];
i,n,m=1e9+7;
main(a){
	for(i=scanf("%d",&n);n/++i;)a=(t[i%2]+=a)*i%m;
	printf("%d",a);
}

92B