จำนวนวิธีในการสวมหมวกที่แตกต่างกันใน C++

สมมติว่ามีคน n คนและหมวก 40 ประเภทที่แตกต่างกันซึ่งมีป้ายกำกับตั้งแต่ 1 ถึง 40 ตอนนี้รายการแบบ 2 มิติจะเรียกว่าหมวก โดยที่ hats[i] คือรายการหมวกทั้งหมด เป็นที่ต้องการของบุคคลที่ i เราต้องหาหลายวิธีที่คน n สวมหมวกที่แตกต่างกัน คำตอบอาจมีขนาดใหญ่มาก ดังนั้นให้ส่งคืนโมดูลคำตอบ 10^9 + 7

ดังนั้น หากอินพุตเป็น [[4,6,2],[4,6]] ผลลัพธ์จะเป็น 4 เนื่องจากมี 4 วิธีให้เลือก ได้แก่ [4,6], [6, 4], [2,4], [2,6].

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

• ม. =10^9 + 7

• กำหนด 2D array dp ขนาด 55 x 2^11

• กำหนดอาร์เรย์ 2 มิติ v

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

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

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้ idx, mask

• ถ้ามาสก์เหมือนกับ req แล้ว −

  • กลับ 1

• ถ้า idx เท่ากับ 42 แล้ว −

  • คืนค่า 0

• ถ้า dp[idx, mask] ไม่เท่ากับ -1 ดังนั้น −

  • ส่งคืน dp[idx, mask]

• ret :=add(ret, แก้(idx + 1, mask))

• สำหรับทุกคนใน v[idx]sk))

  • ถ้า (shift mask i bit ไปทางขวา) เป็นจำนวนเท่ากัน

    • ret =add(ret, แก้(idx + 1, mask OR 2^i))

• dp[idx, mask] :=ยกเลิก

• รีเทิร์น

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

• เริ่มต้น dp ด้วย -1

• n :=ขนาดของ x

• อัปเดต v เพื่อให้มี 50 องค์ประกอบ

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • สำหรับ j ใน x[i]

    • ใส่ i ต่อท้าย v[j]

• req :=(2^n) - 1

• ret :=แก้(0, 0)

• รีเทิร์น

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
int m = 1e9 + 7;
int dp[55][1 << 11];
class Solution {
   public:
   vector<vector<int> > v;
   int req ;
   int add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   int solve(int idx, int mask){
      if (mask == req)
      return 1;
      if (idx == 42)
      return 0;
      if (dp[idx][mask] != -1) {
         return dp[idx][mask];
      }
      int ret = add(ret, solve(idx + 1, mask));
      for (int i : v[idx]) {
         if (!((mask >> i) & 1)) {
            ret = add(ret, solve(idx + 1, mask | (1 << i)));
         }
      }
      return dp[idx][mask] = ret;
   }
   int numberWays(vector<vector<int>>& x){
      memset(dp, -1, sizeof dp);
      int n = x.size();
      v.resize(50);
      for (int i = 0; i < x.size(); i++) {
         for (int j : x[i]) {
            v[j].push_back(i);
         }
      }
      req = (1 << n) - 1;
      int ret = solve(0, 0);
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{4,6,2},{4,6}};
   cout << (ob.numberWays(v));
}

อินพุต

{{4,6,2},{4,6}}

ผลลัพธ์

4