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

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

本文概述

给定三个正整数N, L和R，任务是找出组成大小为N的数组，其中每个元素都在[L, R]范围内，使数组中所有元素的总和能被2整除的方法的个数。

例子：

输入：N = 2, L = 1, R = 3
输出：5可能所有元素之和被2整除的数组为[1、1], [2、2], [1、3], [3、1]和[3, 3]
输入：N = 3, L = 2, R = 2
输出：1

方法：这个想法是找到分别在L和R之间具有0和1模2的余数的计数。可以通过以下方式计算该计数：

我们需要对余数为1模2的范围之间的数字进行计数。F =所需类型范围内的第一个数字L =所需类型范围内的最后一个数字Count =(L – F)/ 2 cnt0, 而cnt1表示介于每种类型。

然后，利用动态规划来解决这一问题。设dp[i][j]表示第一个i数模2等于j的路径数。假设我们需要计算dp[i][0]，那么它将有如下递归关系:dp[i][0] = (cnt0 * dp[i - 1][0] + cnt1 * dp[i - 1][1])。第一项表示在(i - 1)之前余数为0的方式的数量，因此我们可以将cnt0数字放在第i个位置，使余数之和仍然为0。第二项表示到(i - 1)为止余数之和为1的方式数，因此我们可以将cnt1数放在第i个位置，使余数之和为0。同样，我们可以计算dp[i][1]。

最终答案用dp[N][0]表示。

下面是上述方法的实现：

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
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: