原題鏈接

1214. 波動數(shù)列

題目難度：中等

題目來源：第五屆藍(lán)橋杯省賽C++ A組,第五屆藍(lán)橋杯省賽Java A組

題目描述

觀察這個數(shù)列：

1 3 0 2 -1 1 -2 …

這個數(shù)列中后一項總是比前一項增加2或者減少3，且每一項都為整數(shù)。

棟棟對這種數(shù)列很好奇，他想知道長度為 n 和為 s 而且后一項總是比前一項增加 a 或者減少 b 的整數(shù)數(shù)列可能有多少種呢？

輸入格式

共一行，包含四個整數(shù) n,s,a,b，含義如前面所述。

輸出格式

共一行，包含一個整數(shù)，表示滿足條件的方案數(shù)。

由于這個數(shù)很大，請輸出方案數(shù)除以 100000007 的余數(shù)。

數(shù)據(jù)范圍

$1\le n\le 1000$,
$?10^9\le s\le 10^9$,
$1\le a,b\le 10^6$

輸入樣例：

4 10 2 3 

輸出樣例：

2 

樣例解釋

兩個滿足條件的數(shù)列分別是2 4 1 3和7 4 1 -2。

題目分析

這道題的意思很簡單就是長度為 n 和為 s 而且后一項總是比前一項增加 a 或者減少 b 的整數(shù)數(shù)列可能有多少種

我們可以從數(shù)學(xué)角度來看，第一項假設(shè)為$x$，第二項就為$x+d_1$，第三項為$x+d_1+d_2$，以此類推，這里的 d i ∈ { + a , ? b } d_i\in\{+a,-b\} di?∈{+a,?b}，然后一共有$n$項

那么他的前n項和為$nx+(n?1)d_1+(n?2)d_2+?+d_{n?1}=s$

我們可以發(fā)現(xiàn)在這個過程中的變量是非常多的首先x是屬于任意整數(shù)的，其次是每一個d，都有兩種選法，所以我們可以從后往前進(jìn)行推算，因為只要后面的數(shù)字確定了，前面的情況其實也并不算多

我們可以算出來x

$x=\frac{s?((n?1)d_1+(n?2)d_2+?+d_{n?1})}{n}$

任何一組對應(yīng)的d的取值都對應(yīng)了一個x

那么問題就變成了，所有滿足要求的d的取值的方案數(shù)

第一個要求是每一個d都只能取兩種，第二個要求是x必須是整數(shù)，即為分子必須是分母的倍數(shù)

這里有一個名為同余定理的簡化方法，因為需要s減去和與n的模值為0，所以只需要s與和的模n的余數(shù)相同即可，因為相減是可以把余數(shù)減掉的

那么我們還是使用集合思想的動態(tài)規(guī)劃，對于集合$f(i,j)$，他的含義是前i項的和除n的余數(shù)是j的方案數(shù)的集合

那么對于狀態(tài)計算，我們?nèi)匀豢紤]集合劃分，可以劃分成兩個子集，第一種就是最后一項+a的，第二種是最后一項-b的，我們只需要分別求兩邊的情況方案數(shù)相加即可

$f(i?1,(j?i?a)\%n)$文章來源地址http://www.zghlxwxcb.cn/news/detail-793967.html

示例代碼

#include<iostream>
using namespace std;

const int N = 1010,MOD = 100000007;

int f[N][N];
int mod(int a,int b) // 求正余數(shù)
{
    return (a%b+b)%b;
}

int main()
{
    int n,s,a,b;
    cin>>n>>s>>a>>b;
    f[0][0] = 1;
    for(int i=1;i<n;i++)
        for(int j=0;j<n;j++)
        {
            f[i][j] = (f[i-1][mod(j-(n-i)*a,n)]+f[i-1][mod(j+(n-i)*b,n)])%MOD;
        }
    cout<<f[n-1][mod(s,n)]<<'\n';
    return 0;
}

到了這里，關(guān)于每日算法打卡：波動數(shù)列 day 16的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！