杭州网站推广优化公司,wordpress wdone破解,济南公司做网站,做网站维护要多少钱一年题目描述 观察这个数列#xff1a;1 3 0 2 -1 1 -2 …这个数列中后一项总是比前一项增加2或者减少3。 栋栋对这种数列很好奇#xff0c;他想知道长度为 n 和为 s 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢#xff1f; 输入 输入的第一行包含四个整数 n…题目描述 观察这个数列1 3 0 2 -1 1 -2 …这个数列中后一项总是比前一项增加2或者减少3。 栋栋对这种数列很好奇他想知道长度为 n 和为 s 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢 输入 输入的第一行包含四个整数 n s a b含义如前面说述。 1n1000-1,000,000,000s1,000,000,0001a, b1,000,000。 输出 输出一行包含一个整数表示满足条件的方案数。由于这个数很大请输出方案数除以100000007的余数。 样例输入 4 10 2 3 样例输出 2
解题思路 我们不妨设ddd为aaa或者为−b-b−b,则d(a,−b)d (a,-b)d(a,−b),然后我们就知道这个数列是这样的 x,xd1,xd1d2,⋯,xd1d2⋯dn−1x ,xd_1,xd_1d_2,\cdots,xd_1d_2\cdotsd_{n-1}x,xd1,xd1d2,⋯,xd1d2⋯dn−1
这个数列的合为sss,所以我们可以得到 nx(n−1)d1(n−2)d2⋯dn−1snx(n-1)d_1(n-2)d_2\cdotsd_{n-1} snx(n−1)d1(n−2)d2⋯dn−1s
然后得到 s−[(n−1)d1(n−2)d2⋯dn−1]n\frac{s-[(n-1)d1(n-2)d2\cdotsd_{n-1}]}{n}ns−[(n−1)d1(n−2)d2⋯dn−1]xxx
所以我们可以知道s模n与[(n−1)d1(n−2)d2⋯dn−1]模n相等s模n与[(n-1)d_1(n-2)d_2\cdotsd_{n-1}]模n相等s模n与[(n−1)d1(n−2)d2⋯dn−1]模n相等
又因为dnd_ndn (a,−b)(n1,2,3,...,n)(a,-b) (n 1,2,3,...,n)(a,−b)(n1,2,3,...,n),所以我们可以得到 s模n与[d12d2⋯(n−1)dn−1]模n相等s模n与[d_12d_2\cdots(n-1)d_{n-1}]模n相等s模n与[d12d2⋯(n−1)dn−1]模n相等
现在我们设dp[i][j]表示表示要选i个a或者-b且余数为j的所有集合的数量。
那么我们现在思考关系表达式 现在我们要选的是第i项的d意思就是第i项的d是要a,还是-b,在第i项前面的都是已经选好的了所以 我们设第i项前面的d加起来总和为C然后我们可以根据 d12d2⋯(n−1)dn−1d_12d_2\cdots(n-1)d_{n-1}d12d2⋯(n−1)dn−1可以得到 (Ci∗di)模nj(Ci*d_i)模n j(Ci∗di)模nj
那么C模n就等于(j−i∗di)模nj - i*d_i)模nj−i∗di)模n
则得到关系表达式
f[i][j] (f[i-1][get_mod(j-a*i,n)]f[i-1][get_mod(jb*i,n)])%MOD;这里我们之所以对a模b要用(a%bb)%b的形式是因为C中的%与数学上的取模不太一样举个例子
1.C-2%3 -2出现了负数在数组中a[i]i不能为负因此要转换。
2.数学上-2%3 1
所以要用这个公式让C进行数学上的取模(a%bb)%b只要C取模以后得到的结果可能为负数推荐都用公式进行这样的转换 C手写a除以b的正余数
然后想想如何初始化初始化也很简单dp[0][0] 1,他选0项那么总和肯定是0,0模n也是0所以为1
代码如下
#include iostream
using namespace std;
const int N 1010;
int dp[N][N];
const int MOD 100000007;
int get_mod(int a,int b)
{return (a%bb)%b;
}int main()
{int n,s,a,b;cinnsab;dp[0][0] 1;for (int i 1;in;i)for (int j 0;jn;j)dp[i][j] (dp[i-1][get_mod(j-a*i,n)]dp[i-1][get_mod(jb*i,n)])%MOD;coutdp[n-1][get_mod(s,n)]endl;return 0;
}
