欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bzoj3209: 花神的数论题(数位DP)

程序员文章站 2022-07-05 11:19:05
题目: "3209: 花神的数论题" 解析: 二进制的数位DP 因为$[1,n]$中每一个数对应的二进制数是唯一的,我们枚举$1$的个数$k$,计算有多少个数的二进制中有$k$个$1$ 设$n$的二进制一共有$num$位,有$sum[i]$个数的二进制中有$k$个$1$, 答案就是$\prod_{i ......

题目:

3209: 花神的数论题

解析:

二进制的数位dp
因为\([1,n]\)中每一个数对应的二进制数是唯一的,我们枚举\(1\)的个数\(k\),计算有多少个数的二进制中有\(k\)\(1\)
\(n\)的二进制一共有\(num\)位,有\(sum[i]\)个数的二进制中有\(k\)\(1\)
答案就是\(\prod_{i=1}^{num}i^{sum[i]}\)

用数位dp搞一下就好了
\(f[i][j]\)表示到第\(i\)位有\(j\)\(1\)时有多少个数
枚举\(k\),记搜一下。

由于可能会有很多数的二进制中有\(k\)\(1\),所以用快速幂维护一下

相似思路的题还有1799: [ahoi2009]self 同类分布

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int n = 60;
const int mod = 10000007;

int n, m, num;
int digit[n], f[n][n];

int qpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        b >>= 1, a = (a * a) % mod;
    }
    return ans % mod;
}

int dfs(int pos, int sum, int cnt, int limit) {
    if (pos == -1) return sum == cnt;
    if (cnt > sum) return 0;
    if (!limit && ~f[pos][cnt]) return f[pos][cnt];
    int up = limit ? digit[pos] : 1;
    int ans = 0;
    for (int i = 0; i <= up; ++i) 
        ans = ans + dfs(pos - 1, sum, cnt + i, limit && i == up);
    if (!limit) f[pos][cnt] = ans;
    return ans;
}

int divide(int x) {
    int num = 0, ans = 1;
    for ( ; x; x /= 2) digit[num++] = x % 2;
    for (int i = 1; i <= num; ++i) { 
        memset(f, -1, sizeof f);
        ans = (ans * qpow(i, dfs(num - 1, i, 0, 1))) % mod;
    }
    return ans % mod;
}

signed main() {
    cin >> n;
    cout << divide(n);
}