本文概述

• C ++
• Java
• Python3
• C#
• 的PHP

给定三个正整数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 ] = rl + = 1 r - = 1if (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 + 1dp = [[ 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 approachusing 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 ?>

【形成具有给定范围内的整数的数组的方法，以使总和可被2整除】输出如下：

5

推荐阅读

• 

  社保需要交多少年才可以领养老金?养老金是怎么算的
• 

  人造棉是棉绸吗
• 

  教你如何开挂，教你如何自己做挂不用担心被抓
• 

  老竹大方茶的产地及品质特征介绍
• 

  八小时工作制最早出现在哪个国家
• 

  故事里的人——石神与石泓
• 

  家里的小猫得了猫藓,医生照了一下说很严重开了八百多块钱药,请问这个花费正常吗,以后还要花多少钱？
• 

  锦鲤花养殖注意事项 锦鲤水花养殖注意事项
• 

  抖音朋友圈射箭穿心表白图制作教程
• 

  外用药能否治疗早泄 早泄的外用药
• 

  佳能5d拍摄技巧 佳能5ds拍体育
• 

  让龙猫亲近自己的方法有吗
• 

  重庆被起诉了但是实在没有钱还怎么办
• 

  科目4多少分才算合格
• 

  笔记|多线程基础
• 

  用户|为什么iQOO Z3能不让用户做“取舍”？
• 

  FGO情人节三期高难本怎么打 2019女帝情人节高难本攻略
• 

  一辈子闺蜜经典句子有哪些
• 

  大金空调制冷外机不工作怎么办,一般情况就放置在这个位置
• 

  如何搭建直播电商平台，如何做好电商直播平台

• Django教程详细指南介绍
• 如何开始软件测试职业-完整指南！
• 十进制等效项大于或等于K的子字符串的计数
• PHP stream_get_transports()函数用法示例
• 修改给定数组以使奇数和偶数索引元素的总和相同
• 从OpenCV 2到OpenCV 3.x的过渡
• AWS中安全组和网络ACL之间的区别
• 8085程序以n个数字的数组搜索数字
• Android测试（从零开始3—— Instrumented单元测试1）