Question link
Luogu P1466
Question
Title description
For from
1
~
n
1\sim n
The set of consecutive integers from 1 to n can be divided into two subsets, and the sum of the numbers in each set is guaranteed to be equal. For example, if
n
=
3
n=3
n=3, for
{
1
,
2
,
3
}
\{1,2,3\}
{1,2,3} can be divided into two subsets, and the sum of all numbers in each subset is equal:
{
3
}
\{3\}
{3} and
{
1
,
2
}
\{1,2\}
{1,2} is the only division method (exchanging set positions is considered to be the same division plan, so it will not increase the total number of division plans)
if
n
=
7
n=7
n=7, there are four ways to divide the set
{
1
,
2
,
3
,
4
,
5
,
6
,
7
}
\{1,2,3,4,5,6,7 \}
{1,2,3,4,5,6,7}, the sum of the numbers in the subsets of each division method is equal:
{
1
,
6
,
7
}
\{1,6,7\}
{1,6,7} and
{
2
,
3
,
4
,
5
}
\{2,3,4,5\}
{2,3,4,5}
{
2
,
5
,
7
}
\{2,5,7\}
{2,5,7} and
{
1
,
3
,
4
,
6
}
\{1,3,4,6\}
{1,3,4,6}
{
3
,
4
,
7
}
\{3,4,7\}
{3,4,7} and
{
1
,
2
,
5
,
6
}
\{1,2,5,6\}
{1,2,5,6}
{
1
,
2
,
4
,
7
}
\{1,2,4,7\}
{1,2,4,7} and
{
3
,
5
,
6
}
\{3,5,6\}
{3,5,6}
given
n
n
n, your program should output the total number of partitioning plans.
Input format
The input file has only one line and only one integer
n
n
n
Output format
Output the total number of partitioning plans.
Example #1
Sample input #1
7
Sample output #1
4
Tips
【data range】
for
100
%
100\%
100% data,
1
≤
n
≤
39
1\le n\le 39
1≤n≤39.
Translation from NOCOW
USACO 2.2
Question meaning
There is a positive integer
n
n
n , there is an existing
1
~
n
1\sim n
Divide the set of continuous integers from 1 to n into two sets, make the sum of the elements of the two sets equal, and find out how many partitioning plans there are (exchanging the positions of the sets is considered to be the same division plan, so it will not increase the total number of division plans )
Ideas
Let’s judge one hand first, if
1
~
n
1\sim n
If the sum of the elements of a continuous set of integers from 1 to n is an odd number, then this set cannot be divided in the above way in any case, and the output
0
0
0
Treat the elements in the set as stages, using
01
01
01 Knapsack enumerates some elements and puts them into the previous set, making the sum of the elements of the previous set equal to the sum of the elements of the next set, and classifying the sum of the elements of the previous set.
but
d
p
[
i
]
dp[i]
dp[i] represents the sum of the elements of the previous set as
i
i
Number of options at time i
If the current element
i
i
i is not put into the previous set, then
d
p
dp
The dp array does not need to be updated, skip
If the current element
i
i
i is put into the previous set, then
d
p
[
i
]
+
=
d
p
[
i
?
j
]
dp[i] + =dp[i-j]
dp[i] + =dp[i?j]
And also to
d
p
dp
dp array initialization
d
p
[
0
]
=
1
dp[0]=1
dp[0]=1
See the code for details
#include<bits/stdc + + .h>
using namespace std;
#define int long long
int dp[(1 + 40)*40/2]={<!-- -->1LL},sum,n;
signed main(){<!-- -->
scanf("%lld", & amp;n);
sum=(1 + n)*n/2;//Sum of elements
if(sum%2){<!-- -->//The sum of the elements in the set is an odd number and cannot be divided
printf("0");
return 0;
}
for(int i=1;i<=n;i + + ){<!-- -->
for(int j=sum/2;j>=i;j--){<!-- -->//Just fill in the previous set, and the next set will come out, so use sum/2
dp[j] + =dp[j-i];//01 backpack - state transition equation
}
}
printf("%lld",dp[sum/2]/2);//The output must be divided by 2 because there are two sets (exchanging the set positions is considered to be the same division scheme, so it will not increase the division total number of plans)
return 0;
}