讨论/题目交流/🐱 第 25 场夜喵双周赛/
🐱 第 25 场夜喵双周赛
展开讨论
力扣 (LeetCode)发起于 2020-05-02

我这样写哪里错了?

typedef long long LL;

const LL MOD = 1e9 + 7;

LL dp[15][45][2]; // 0 方案数 1 状态

class Solution {
public:
    int n;
    int numberWays(vector<vector<int>>& hats) {
        n = hats.size();
        memset(dp, 0, sizeof(dp));
        
        for (auto hat : hats[0]) {
            dp[0][hat][0] = 1;
            dp[0][hat][1] = (1 << hat);
        }
        
        for (int i = 1; i < n; i++) {
            for (auto hat : hats[i]) {
                for (auto h : hats[i - 1]) {
                    LL status = dp[i - 1][h][1];
                    if ((status & (1 << hat)) == 0) {
                        (dp[i][hat][0] += dp[i - 1][h][0]) %= MOD;
                        dp[i][hat][1] = (status | (1 << hat));
                    }
                }
            }
        }
        
        LL ans = 0;
        for (auto hat : hats[n - 1]) {
            (ans += dp[n - 1][hat][0]) %= MOD;
        }
        
        return (int)(ans % MOD);
    }
    
};
展开全部 29 讨论