[蓝桥杯 2014 省 A] 波动数列

容我菜菲说一句，全网前排题解都是rubbish，当然洛谷某些也是litter

不好意思，最近背单词背了很多垃圾的英文，正题开始

[蓝桥杯 2014 省 A] 波动数列

题目描述

输入格式

输入的第一行包含四个整数 $n,s,a,b$，含义如前面说述。

输出格式

输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以 $100000007$ 的余数。

样例 #1

样例输入 #1

4 10 2 3

样例输出 #1

2

提示

思路

假设首项为a1，操作为p，那么 a1 + (a1+p) + (a1+2 * p) + … + [a1+(n-1) * p] = s；
整理式子，得：n*a1 + [p + 2 * p + … + (n-1) * p] = s ；
令K= [p + 2 * p + … + (n-1) * p] ，一共是n-1项
则 a1=(s-K) / n；
也就是说，求s%n==k%n 的个数
那我们就对k=[p + 2 * p + … + (n-1)*p] 当作背包好了

上面看不懂可以转战别人的题解，尊嘟。

一般来说，这个题有两种状态转移，一种反推，一种正推，反正最后的结果看的是余数，小于n的。

这是正推：

dp[i][j]表示，进行第i次+a或-b操作时，整个长度（长度为n-1）的和的余数等于j的方案数
已知前一项（i-1项）的余数为j，求第i项+a，-b的余数；
由于前一项＋a，那么后面的每一项都会+a，所以求和就要乘以后面的项数；
同理-b也是。

dp[i][__(j+a*(n-i+1))]+=dp[i-1][__(j)];
dp[i][__(j-b*(n-i+1))]+=dp[i-1][__(j)];

这是反推：（与正推相比，只有状态转移方程不同）

后一项（i+1项）的余数为j，那么肯定是当前项操作后转移过来的。
我们现在把最后一项当第一项看，第一项当最后一项，
那么i就是我们的原来排列的后缀长度，换句话就是，我在这里进行了+a操作，后面（包括当前项）的长度刚好为i，所以有i * a，同理，-b也是。
那么前面的一项就是j-a * i的余数（我想要成为j，是从（ j - a * i ）+ a * i 变成的）

dp[i][j]=dp[i-1][__(j-a*i)]+dp[i-1][__(j+b*i)];

最后

不要忘记取模，mod=100000007(1e8+7)
因为减法可能会带来负数，所以写了个__()的函数用来取模
反推的代码确实短小精悍，但是能正确理解的不多。我也是问了很多大佬才理解的，某些题解确实garbage，别喷我，喷就是你对
欢迎新的题解出现 ^ v ^ ~

Code

ll dp[1005][1005];

ll __(ll x)
{
	return (x%n+n)%n;
}
void solve()
{
	ll s,a,b;
	cin>>n>>s>>a>>b;
	
	
	dp[1][0]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<n;j++)
		{
			(dp[i][__(j+a*(n-i+1))]+=dp[i-1][__(j)])%=mod;
			(dp[i][__(j-b*(n-i+1))]+=dp[i-1][__(j)])%=mod;
		}
	}
	
	cout<<dp[n][__(s)];
}