home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

จำนวนวิธีในการระบายสี N × 3 Grid ในโปรแกรม C++

สมมติว่าเรามีตารางที่มีขนาด n x 3 และเราต้องการลงสีทุกเซลล์ในตารางด้วยสีใดสีหนึ่งจากสามสี โดยสีที่จะใช้คือ แดง เหลือง และเขียว

ขณะนี้มีข้อจำกัด นั่นคือไม่มีเซลล์ที่อยู่ติดกันสองเซลล์ที่มีสีเหมือนกัน เรามี n จำนวนแถวของตาราง สุดท้าย เราต้องหาจำนวนวิธีที่เราสามารถลงสีตารางนี้ได้ คำตอบอาจมีขนาดใหญ่มาก ให้คืนค่าเป็นโมดูโล 10^9 + 7.

ดังนั้นหากอินพุตเท่ากับ 1 เอาต์พุตจะเป็น 12

จำนวนวิธีในการระบายสี N × 3 Grid ในโปรแกรม C++

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • ม. =10^9 + 7

  • กำหนดฟังก์ชัน add() ซึ่งจะใช้เวลา a, b,

  • กลับ ((a mod m) + (b mod m)) mod m

  • จากวิธีหลัก ให้ทำดังต่อไปนี้ −

  • a123 :=6, a121 =6

  • สำหรับการเริ่มต้น i :=2 เมื่อฉัน −=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ −

    • b121 :=เพิ่ม (3 * a121, 2 * a123)

    • b123 :=เพิ่ม (2 * a121, 2 * a123)

    • a121 :=b121

    • a123 :=b123

  • กลับเพิ่ม (a123, a121)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 + 7;
class Solution {
public:
   lli add(lli a, lli b){
      return ((a % mod) + (b % mod)) % mod;
   }
   int numOfWays(int n){
      lli a123 = 6, a121 = 6;
      lli b123, b121;
      for (int i = 2; i <= n; i++) {
         b121 = add(3 * a121, 2 * a123);
         b123 = add(2 * a121, 2 * a123);
         a121 = b121;
         a123 = b123;
      }
      return add(a123, a121);
   }
};
main(){
   Solution ob;
   cout << (ob.numOfWays(3));
}

อินพุต

3

ผลลัพธ์

246