1 3 0 2 -1 1 -2 ...
这个数列中后一项总是比前一项增加2或者减少3。
栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢？ 输入格式 输入的第一行包含四个整数 n s a b，含义如前面说述。 输出格式 输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以100000007的余数。 样例输入 4 10 2 3 样例输出 2 样例说明 这两个数列分别是2 4 1 3和7 4 1 -2。
解题思路: 假设P = (a or -b)，第一项为x，则 x + x+P + x+2P + ... + x+(n-1)P = s , nx + (n-1)n/2 * P = s , (s - ( n-1)n/2*P ) % n == 0 (x为整数) 这里用P其实不够准确，若第二项选择+a，则第三项是在 x+a的基础上选择+a / -b, 所以不同项选择的“权重“不同，第二项选择+a后剩下的项 都相当于+a,这时只要反过来表示才是准确的: x + (n-1)P + (n-1)P + ... + P = s. 假设a总共和有k1项，b有k2项，那么 k1 + k2 == (n-1)n/2 , 且满足 ( s - k1*a + k2*b ) %n ==0 ，所以问题转化为计算对于k1(0<=k1<=(n-1)n/2), 有多少种求和方案:<k1的不同且相加为k1的方案有多少的问题。 dp解决：另dp[ i ][ j ] :表示前i项a相加和为j的方案数。为方便起见，i的权重即为i。此时与01背包问题类似:若 i>j,则 i 不能加入,dp[ i ][ j ] = dp[ i-1][ j ], 若 i<j, 则dp[ i ][ j ] = dp[ i-1][ j ] + dp[ i-1 ][ j-i ] .不过对于100%的数据，1<=n<=1000，-1,000,000,000<=s<=1,000,000,000，开不了这么大的二维数组， 而dp[ i ] 只与 dp[ i-1 ]有关，可以用两行滚动数组解决。 实现代码:
1 #include<cstdio>
2
3 typedef long long int ll;
4
5 const int Max_N = 1000;
6 const ll Max_S = 1000000;
7 const ll mod = 100000007;
8
9 ll n,s,a,b;
10
11 int dp[2][Max_S/2];
12
13 void solve()
14 {
15 dp[0][0] = 1; //初始条件 凑成0个a的方案数为1
16 int flag = 1;
17 //dp[i][j]:前i项可以凑成j的方案数
18 for( ll i=1; i<n; i++ )
19 {
20 int flag_ = 1 - flag;// 0->1 1->0
21 for( ll j=0; j<=(i+1)*i/2; j++ )
22 {
23 if( i>j ){
24 dp[flag][j] = dp[flag_][j];
25 }
26 else{
27 dp[flag][j] = (dp[flag_][j]+dp[flag_][j-i])%mod;
28 }
29 }
30 flag = flag_;
31 }
32
33 ll S = (n-1)*n/2;
34 ll res = 0;
35 for( ll k=0; k<=S; k++ )
36 {
37 ll k_ = S - k;
38 if( (s-k*a+k_*b)%n==0 ){
39 res = (res + dp[1-flag][k])%mod;
40 }
41 }
42 printf("%lld\n",res);
43 }
44
45 int main()
46 {
47 scanf("%lld%lld%lld%lld",&n,&s,&a,&b);
48
49 solve();
50
51 return 0;
52 }
View Code
上解题思路是把所有a项数的方案计算出来，依次判断各项数下是否满足条件。另一个思路参考 https://www.cnblogs.com/mohari/p/13799761.html (更加简洁优美)
因为有 ( s - k1*a + k2*b ) %n ==0 --> s%n == (k1*a- k2*b)%n 即P的和与s同余。则问题转变为求P和与s同余的方案数。设dp[ i ][ j ]:前i项P和%n后==j的方案个数。
dp[ i ][ j ] 有前 i -1 项和 +i*a或者-i*b后%n==j得到。设前i-1项和为c:
c + i*a ≡ j (mod n) --> c ≡ j - i*a(mod n)
c - i*b ≡ j( mod n) --> c ≡ j + i*b( mod n)
所以dp[ i ][ j ] = ( dp[i-1][ (j-ai*+n)%n ] + dp[ i-1 ][ (j+i*b)%n ])
实现代码:
1 #include<cstdio>
2
3 typedef long long ll;
4
5 const int Max_N = 1000;
6 const int mod = 100000007;
7
8 //输入
9 ll n,s,a,b;
10
11 int dp[Max_N][Max_N];
12
13 void solve()
14 {
15 dp[0][0] = 1;
16
17 for( int i=1; i<n; i++ )
18 {
19 for( int j=0; j<n; j++ )
20 {
21 dp[i][j] = (dp[i-1][((j-i*a)%n+n)%n]+dp[i-1][(j+i*b)%n])%mod;
22 }
23 }
24
25 printf("%d\n",dp[n-1][((s%n)+n)%n]);
26 }
27
28 int main()
29 {
30 scanf("%lld%lld%lld%lld",&n,&s,&a,&b);
31
32 solve();
33
34 return 0;
35 }
View Code
负数取余:https://www.cnblogs.com/widerg/p/7208041.html?utm_source=itdadao&utm_medium=referral 避免余数出现负数: ( a%b+b)%b