AcWing 1214. 波动数列（有公式详细推导）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1214. 波动数列（有公式详细推导）原题链接中等

作者：

改革春风吹满地 , 2021-11-07 12:53:57 , 所有人可见 , 阅读 5312

81

43

==题解==：
此题应该是一个组合问题
设这个数列第一项为x，设 d ∈{ +a, -b } ，则长度为n的序列所有的项为
$x , x + d_1, x + d_2, x + d_3, … , x + d_{n-1}$
他的和为 $nx + (n-1)d_1 + (n-2)d_2 + (n-3)d_3 + … + d_n-1 = s$
因为x的大小我们无法确定，所以我们把公式变形如下
$x =\frac{( s-( (n-1)d_1+ (n-2)d_2 + (n-3)d_3 + … + d_{n-1}) )}{n}$
求满足这个式子的方案数有多少，因为x一定是整数，所以 $( s-( (n-1)d_1+ (n-2)d_2 + (n-3)d_3 + … + d_{n-1}) )$ % n一定为 0 ，因此推出s % n == $(n-1)d_1+ (n-2)d_2 + (n-3)d_3 + … + d_{n-1}$ 的和 % n，也就是两者的模n的余数必须相同
s是确定的，
所以我们最后就是要求 $(n-1)d_1+ (n-2)d_2 + (n-3)d_3 + … + d_{n-1}$ 这个式子的所有可能的和模n的余数是s%n的结果数
——————————————————分割线——————————————————————
是一个dp组合问题：
状态表示：设 $f[i][j]$ 为选了i个数，前 i 个 d 的和模 n 的余数为 j 的集合的数量
明确目标：最后求得是 $f[n-1][s\%n]$ 的值
递推关系：
第 i 次选择时可以选 +a 也可以选 -b
如果选 + a，前i个数的和为
$[(n-1)d_1~ + (n-2)d_2~ +… +(n-(i-1))d_{i-1}+(n-i)a]\%n≡j\%n$
$(n-1)d_1~ + (n-2)d_2~ +… +(n-(i-1))d_{i-1}≡j-(n-i)a$
因为f[i][j]代表的是组合数量，因为j-(n-i)a是已经确定的数值，所以变化的数量在前面的和里面，可以推出
所以 $f[i][j] = f[i-1][j-a(n-i)]$
同理，如果选-b, $f[i][j] = f[i-1][j+b(n-i)]$
$f[i][j] = f[i-1][j+b(n-i)]+f[i-1][j-a(n-i)]$
在这里插入图片描述

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010,MOD = 100000007;

int f[N][N]; //设f[i][j]为前i个数的总和模n余数为j的集合数
int get_mod(int a,int b) //求a除以b的正余数
{
    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][get_mod(j-a*(n-i),n)] + f[i-1][get_mod(j+b*(n-i),n)] ) % MOD;
         }
    }
    cout<<f[n-1][get_mod(s,n)]<<endl;
    return 0;
}

40 评论

学习中 2022-02-01 18:51

第四行表示写错了吧，应该是 $x,x+d_{1},x+d_{1}+d_{2},…,x+d_{1}+d_{2}…+d_{n-1}\quad d_{i}=\{a,-b\}$

WAsbry 2021-11-09 14:08

我想的是假设前i-1项总和为s那么我们需要得到前i-1项的余数，所以先得到前i-1项的和S给S取余后得到S的余数。
就是[S+(n-i)a]%n=j; 你的题解里（大概）是[S+(n-i)a]%n=j%n;这里不太懂了 = =

改革春风吹满地 2021-11-10 09:52

你说的也是对的，只要能推出那个递推式就行

改革春风吹满地 2021-11-10 09:54 回复了改革春风吹满地的评论

不影响因为 j 本身也是模 n 得到的小于 n 的数

WAsbry 2021-11-10 19:07 回复了改革春风吹满地的评论

对对对！啊！对对对！确实！
我懂了~

WAsbry 2021-11-10 19:07 回复了改革春风吹满地的评论

感谢！

做ac梦w 2022-03-13 20:03 回复了 WAsbry 的评论

大佬们还是不太懂波动数列这个j-a*(n-i)的含义

改革春风吹满地 2022-03-27 18:00 回复了做ac梦w 的评论

可以把它当做常量理解

做ac梦w 2022-03-27 18:36 回复了改革春风吹满地的评论

好的谢谢大佬

69岁扶墙coding 2023-03-03 10:23

我想知道他是怎么推出来j+(n-1)*b与前i-1项的和模n余数相同的

章鱼泰酷辣 2023-03-21 09:44

我也想知道

执中 2023-03-21 12:22 回复了章鱼泰酷辣的评论

记前i项的和为x,则有 x%n=j ,第i项为 -(n-1)b , 前i项的和为 x-(-(n-1)b)即 x+(n-1)b , 而 x+(n-1)b % n = j + (n-1)b % n
就是 x+(n-1)b 在模n的情况下同余于 x%n + (n-1)*b，数论里的一些性质，对于加法,减法,乘法什么时候取模不影响最终取模的结果

执中 2023-03-21 12:24 回复了章鱼泰酷辣的评论

举个例子的话, 8%5=3. (8+6)%5=4 == (8%5+6)%5 == (8%5+6%5）% 5

yjprolus 2023-03-29 17:26 回复了执中的评论

还有(a + b%n) % n == (a + b) % n这种吗，没证出来，请问有链接吗
我看到的只有(a %n + b % n) % n == (a + b) % n
f[i][j] = (f[i - 1][get_mod(j - a(n - i) % n, n)] + f[i - 1][get_mod(j + b(n - i) % n, n)]) % mod这种更严谨一些吧

执中 2023-03-30 07:59 回复了 yjprolus 的评论

这个我是记得之前看评论区有人提到过什么时候取模都不会影响取模的结果。证明的话,我自己证了一下.
(a+b%p)%p=(a%p+b%p%p)%p=(a%p+b%p)%p,不知道严不严谨

alanQAQ 2023-03-31 14:32 回复了执中的评论

这些其实都是数论很基础的知识…在哪看我也不知道怎么说,可以搜索模和同余相关的知识,或者你可以直接找一本信安数学基础,里面会有

我荆轲 2022-04-01 15:49

f[i][j]应该是表示选了前i-1个数，i个d吧

WAsbry 2021-11-09 14:03

兄弟你好：我看了前面几篇题解，他们没讲清楚f[i][j]=f[i−1][j−a(n−i)]f[i][j]=f[i−1][j−a(n−i)] 这个状态转移方程。[(n−1)d1 +(n−2)d2 +…+(n−i−1)di+1+(n−i)a]%n≡j%n 你这里左边的j不是应该表示余数嘛，为什么又给j%n。。这里看不太懂了！