# 形成具有给定范围内的整数的数组的方法，以使总和可被2整除

2021年5月15日18:28:57 发表评论 870 次浏览

## C ++

``````//C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

//Function to return the number of ways to
//form an array of size n such that sum of
//all elements is divisible by 2
int countWays( int n, int l, int r)
{
int tL = l, tR = r;

//Represents first and last numbers
//of each type (modulo 0 and 1)
int L[2] = { 0 }, R[2] = { 0 };
L[l % 2] = l, R[r % 2] = r;

l++, r--;

if (l <= tR && r>= tL)
L[l % 2] = l, R[r % 2] = r;

//Count of numbers of each type between range
int cnt0 = 0, cnt1 = 0;
if (R[0] && L[0])
cnt0 = (R[0] - L[0]) /2 + 1;
if (R[1] && L[1])
cnt1 = (R[1] - L[1]) /2 + 1;

int dp[n][2];

//Base Cases
dp[1][0] = cnt0;
dp[1][1] = cnt1;
for ( int i = 2; i <= n; i++) {

//Ways to form array whose sum upto
//i numbers modulo 2 is 0
dp[i][0] = (cnt0 * dp[i - 1][0]
+ cnt1 * dp[i - 1][1]);

//Ways to form array whose sum upto
//i numbers modulo 2 is 1
dp[i][1] = (cnt0 * dp[i - 1][1]
+ cnt1 * dp[i - 1][0]);
}

//Return the required count of ways
return dp[n][0];
}

//Driver Code
int main()
{
int n = 2, l = 1, r = 3;
cout <<countWays(n, l, r);

return 0;
}``````

## Java

``````//Java implementation of the approach
class GFG
{

//Function to return the number of ways to
//form an array of size n such that sum of
//all elements is divisible by 2
static int countWays( int n, int l, int r)
{
int tL = l, tR = r;

//Represents first and last numbers
//of each type (modulo 0 and 1)
int [] L = new int [ 3 ];
int [] R = new int [ 3 ];
L[l % 2 ] = l;
R[r % 2 ] = r;

l++;
r--;

if (l <= tR && r>= tL)
{
L[l % 2 ] = l;
R[r % 2 ] = r;
}

//Count of numbers of each type between range
int cnt0 = 0 , cnt1 = 0 ;
if (R[ 0 ]> 0 && L[ 0 ]> 0 )
cnt0 = (R[ 0 ] - L[ 0 ]) /2 + 1 ;
if (R[ 1 ]> 0 && L[ 1 ]> 0 )
cnt1 = (R[ 1 ] - L[ 1 ]) /2 + 1 ;

int [][] dp = new int [n + 1 ][ 3 ];

//Base Cases
dp[ 1 ][ 0 ] = cnt0;
dp[ 1 ][ 1 ] = cnt1;
for ( int i = 2 ; i <= n; i++)
{

//Ways to form array whose sum upto
//i numbers modulo 2 is 0
dp[i][ 0 ] = (cnt0 * dp[i - 1 ] [ 0 ]
+ cnt1 * dp[i - 1 ][ 1 ]);

//Ways to form array whose sum upto
//i numbers modulo 2 is 1
dp[i][ 1 ] = (cnt0 * dp[i - 1 ][ 1 ]
+ cnt1 * dp[i - 1 ][ 0 ]);
}

//Return the required count of ways
return dp[n][ 0 ];
}

//Driver Code
public static void main(String[] args)
{
int n = 2 , l = 1 , r = 3 ;
System.out.println(countWays(n, l, r));
}
}

//This code is contributed by Code_Mech.``````

## Python3

``````# Python3 implementation of the approach

# Function to return the number of ways to
# form an array of size n such that sum of
# all elements is divisible by 2
def countWays(n, l, r):

tL, tR = l, r

# Represents first and last numbers
# of each type (modulo 0 and 1)
L = [ 0 for i in range ( 2 )]
R = [ 0 for i in range ( 2 )]

L[l % 2 ] = l
R[r % 2 ] = r

l + = 1
r - = 1

if (l <= tR and r> = tL):
L[l % 2 ], R[r % 2 ] = l, r

# Count of numbers of each type
# between range
cnt0, cnt1 = 0 , 0
if (R[ 0 ] and L[ 0 ]):
cnt0 = (R[ 0 ] - L[ 0 ]) //2 + 1
if (R[ 1 ] and L[ 1 ]):
cnt1 = (R[ 1 ] - L[ 1 ]) //2 + 1

dp = [[ 0 for i in range ( 2 )]
for i in range (n + 1 )]

# Base Cases
dp[ 1 ][ 0 ] = cnt0
dp[ 1 ][ 1 ] = cnt1
for i in range ( 2 , n + 1 ):

# Ways to form array whose sum
# upto i numbers modulo 2 is 0
dp[i][ 0 ] = (cnt0 * dp[i - 1 ][ 0 ] +
cnt1 * dp[i - 1 ][ 1 ])

# Ways to form array whose sum upto
# i numbers modulo 2 is 1
dp[i][ 1 ] = (cnt0 * dp[i - 1 ][ 1 ] +
cnt1 * dp[i - 1 ][ 0 ])

# Return the required count of ways
return dp[n][ 0 ]

# Driver Code
n, l, r = 2 , 1 , 3
print (countWays(n, l, r))

# This code is contributed
# by Mohit Kumar``````

## C#

``````//C# implementation of the approach

using System;

class GFG
{

//Function to return the number of ways to
//form an array of size n such that sum of
//all elements is divisible by 2
static int countWays( int n, int l, int r)
{
int tL = l, tR = r;

//Represents first and last numbers
//of each type (modulo 0 and 1)
int [] L = new int [3];
int [] R = new int [3];
L[l % 2] = l;
R[r % 2] = r;

l++;
r--;

if (l <= tR && r>= tL)
{
L[l % 2] = l;
R[r % 2] = r;
}

//Count of numbers of each type between range
int cnt0 = 0, cnt1 = 0;
if (R[0]> 0 && L[0]> 0)
cnt0 = (R[0] - L[0]) /2 + 1;
if (R[1]> 0 && L[1]> 0)
cnt1 = (R[1] - L[1]) /2 + 1;

int [, ] dp= new int [n + 1, 3];

//Base Cases
dp[1, 0] = cnt0;
dp[1, 1] = cnt1;
for ( int i = 2; i <= n; i++)
{

//Ways to form array whose sum upto
//i numbers modulo 2 is 0
dp[i, 0] = (cnt0 * dp[i - 1, 0]
+ cnt1 * dp[i - 1, 1]);

//Ways to form array whose sum upto
//i numbers modulo 2 is 1
dp[i, 1] = (cnt0 * dp[i - 1, 1]
+ cnt1 * dp[i - 1, 0]);
}

//Return the required count of ways
return dp[n, 0];
}

//Driver Code
static void Main()
{
int n = 2, l = 1, r = 3;
Console.WriteLine(countWays(n, l, r));
}
}

//This code is contributed by mits``````

## 的PHP

``````<?php
//PHP implementation of the approach

//Function to return the number of ways to
//form an array of size n such that sum of
//all elements is divisible by 2
function countWays( \$n , \$l , \$r )
{
\$tL = \$l ;
\$tR = \$r ;

\$L = array_fill (0, 2, 0);
\$R = array_fill (0, 2, 0);

//Represents first and last numbers
//of each type (modulo 0 and 1)
\$L [ \$l % 2] = \$l ;
\$R [ \$r % 2] = \$r ;

\$l ++;
\$r --;

if ( \$l <= \$tR && \$r>= \$tL )
{
\$L [ \$l % 2] = \$l ;
\$R [ \$r % 2] = \$r ;
}

//Count of numbers of each type
//between range
\$cnt0 = 0;
\$cnt1 = 0;
if ( \$R [0] && \$L [0])
\$cnt0 = ( \$R [0] - \$L [0]) /2 + 1;

if ( \$R [1] && \$L [1])
\$cnt1 = ( \$R [1] - \$L [1]) /2 + 1;

\$dp = array ();

//Base Cases
\$dp [1][0] = \$cnt0 ;
\$dp [1][1] = \$cnt1 ;
for ( \$i = 2; \$i <= \$n ; \$i ++)
{

//Ways to form array whose sum upto
//i numbers modulo 2 is 0
\$dp [ \$i ][0] = ( \$cnt0 * \$dp [ \$i - 1][0] +
\$cnt1 * \$dp [ \$i - 1][1]);

//Ways to form array whose sum upto
//i numbers modulo 2 is 1
\$dp [ \$i ][1] = ( \$cnt0 * \$dp [ \$i - 1][1] +
\$cnt1 * \$dp [ \$i - 1][0]);
}

//Return the required count of ways
return \$dp [ \$n ][0];
}

//Driver Code
\$n = 2;
\$l = 1;
\$r = 3;

echo countWays( \$n , \$l , \$r );

//This code is contributed by Ryuga
?>``````

``5``