題目描述
觀察這個(gè)數(shù)列：1 3 0 2 -1 1 -2 …這個(gè)數(shù)列中后一項(xiàng)總是比前一項(xiàng)增加2或者減少3。
棟棟對(duì)這種數(shù)列很好奇，他想知道長(zhǎng)度為 n 和為 s 而且后一項(xiàng)總是比前一項(xiàng)增加a或者減少b的整數(shù)數(shù)列可能有多少種呢？
輸入
輸入的第一行包含四個(gè)整數(shù) n s a b，含義如前面說(shuō)述。
1<=n<=1000，-1,000,000,000<=s<=1,000,000,000，1<=a, b<=1,000,000。
輸出
輸出一行，包含一個(gè)整數(shù)，表示滿(mǎn)足條件的方案數(shù)。由于這個(gè)數(shù)很大，請(qǐng)輸出方案數(shù)除以100000007的余數(shù)。
樣例輸入
4 10 2 3
樣例輸出
2

解題思路：
我們不妨設(shè)$d$為$+a$或者為$?b$,則$d=(+a,?b)$,然后我們就知道這個(gè)數(shù)列是這樣的：
$x,x+d_1,x+d_1+d_2,?,x+d_1+d_2+?+d_{n?1}$

這個(gè)數(shù)列的合為$s$,所以我們可以得到：
$nx+(n?1)d_1+(n?2)d_2+?+d_{n?1}=s$

然后得到：
$\frac{s?[(n?1)d1+(n?2)d2+?+d_{n?1}]}{n}$$=$$x$

所以我們可以知道$s模n與[(n?1)d_1+(n?2)d_2+?+d_{n?1}]模n相等$

又因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$d_n$ = $(+a,?b)(n=1,2,3,...,n)$,所以我們可以得到：
$s模n與[d_1+2d_2+?+(n?1)d_{n?1}]模n相等$

現(xiàn)在我們?cè)O(shè)dp[i][j]表示表示要選i個(gè)a或者-b且余數(shù)為j的所有集合的數(shù)量。

那么我們現(xiàn)在思考關(guān)系表達(dá)式：
現(xiàn)在我們要選的是第i項(xiàng)的d，意思就是第i項(xiàng)的d是要+a,還是-b,在第i項(xiàng)前面的，都是已經(jīng)選好的了，所以：

我們?cè)O(shè)第i項(xiàng)前面的d加起來(lái)總和為C，然后我們可以根據(jù)
$d_1+2d_2+?+(n?1)d_{n?1}$，可以得到：
$(C+i?d_i)模n=j$

那么C模n就等于($j?i?d_i)模n$

則得到關(guān)系表達(dá)式：

f[i][j] = (f[i-1][get_mod(j-a*i,n)]+f[i-1][get_mod(j+b*i,n)])%MOD;

這里我們之所以對(duì)a模b要用(a%b+b)%b的形式，是因?yàn)镃++中的%與數(shù)學(xué)上的取模不太一樣，舉個(gè)例子：

1.C++：-2%3 = -2，出現(xiàn)了負(fù)數(shù)，在數(shù)組中a[i]，i不能為負(fù)，因此要轉(zhuǎn)換。

2.數(shù)學(xué)上：-2%3 = 1

所以要用這個(gè)公式讓C++進(jìn)行數(shù)學(xué)上的取模(a%b+b)%b，只要C++取模以后得到的結(jié)果可能為負(fù)數(shù)，推薦都用公式進(jìn)行這樣的轉(zhuǎn)換：
C++手寫(xiě)a除以b的正余數(shù)

然后想想如何初始化，初始化也很簡(jiǎn)單，dp[0][0] = 1,他選0項(xiàng)，那么總和肯定是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%b+b)%b; }int main() {int n,s,a,b;cin>>n>>s>>a>>b;dp[0][0] = 1;for (int i = 1;i<n;i++)for (int j = 0;j<n;j++)dp[i][j] = (dp[i-1][get_mod(j-a*i,n)]+dp[i-1][get_mod(j+b*i,n)])%MOD;cout<<dp[n-1][get_mod(s,n)]<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯]波动数列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。