邱窕
查看原帖
邱窕
466525
Anaxagoras楼主2024/11/1 19:36
#include <bits/stdc++.h>
#define int long long
#define inf INT_MAX
#define N 105
#define M 7
#define K 25
#define mod 1000000007
using namespace std;
inline int r() {int x; cin >> x; return x;}
inline void w(int x) {cout << x << '\n';}
inline void W(int x) {cout << x << ' ';}
int sta[1 << M];
int dp[2][1 << M][K];
inline int get(int x) {
    int tot = 0;
    while (x) tot ++, x -= x & (-x);
    return tot;
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m = r(), n = r(), k = r();
    for (int i = 0; i < (1 << m); i ++) sta[i] = get(i), dp[1][i][sta[i]] = 1;
    for (int i = 2; i <= n; i ++)
        for (int j = 0; j < (1 << m); j ++)
            for (int x = 0; x < (1 << m); x ++) {
                if (!(j & (x << 2) || (j << 2) & x))
                    for (int l = sta[j]; l <= k; l ++)
                        dp[i % 2][j][l] = (dp[i % 2][j][l] + dp[(i - 1) % 2][x][l - sta[j]]) % mod;
                if (j == (1 << m) - 1)
                    for (int l = 0; l <= k; l ++)
                        dp[(i - 1) % 2][x][l] = 0;
            }
    int ans = 0;
    for (int i = 0; i < (1 << m); i ++) ans = (ans + dp[n % 2][i][k]) % mod;
    w(ans);
    return 0;
}
2024/11/1 19:36
加载中...