家居网站建设精英,站内推广的方法和工具,腾达建设网站,建筑工人招聘网站怎么做容我菜菲说一句#xff0c;全网前排题解都是rubbish#xff0c;当然洛谷某些也是litter
不好意思#xff0c;最近背单词背了很多垃圾的英文#xff0c;正题开始
[蓝桥杯 2014 省 A] 波动数列
题目描述 输入格式
输入的第一行包含四个整数 n , s , a , b n,s,a,b n,s,a…容我菜菲说一句全网前排题解都是rubbish当然洛谷某些也是litter
不好意思最近背单词背了很多垃圾的英文正题开始
[蓝桥杯 2014 省 A] 波动数列
题目描述 输入格式
输入的第一行包含四个整数 n , s , a , b n,s,a,b n,s,a,b含义如前面说述。
输出格式
输出一行包含一个整数表示满足条件的方案数。由于这个数很大请输出方案数除以 100000007 100000007 100000007 的余数。
样例 #1
样例输入 #1
4 10 2 3样例输出 #1
2提示 思路 假设首项为a1操作为p那么 a1 (a1p) (a12 * 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%nk%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][__(ja*(n-i1))]dp[i-1][__(j)];
dp[i][__(j-b*(n-i1))]dp[i-1][__(j)];这是反推与正推相比只有状态转移方程不同 后一项i1项的余数为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][__(jb*i)];最后 不要忘记取模mod100000007(1e87) 因为减法可能会带来负数所以写了个__()的函数用来取模 反推的代码确实短小精悍但是能正确理解的不多。我也是问了很多大佬才理解的某些题解确实garbage别喷我喷就是你对 欢迎新的题解出现 ^ v ^ ~ Code
ll dp[1005][1005];ll __(ll x)
{return (x%nn)%n;
}
void solve()
{ll s,a,b;cinnsab;dp[1][0]1;for(int i2;in;i){for(int j0;jn;j){(dp[i][__(ja*(n-i1))]dp[i-1][__(j)])%mod;(dp[i][__(j-b*(n-i1))]dp[i-1][__(j)])%mod;}}coutdp[n][__(s)];
}
