menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[思维+背包]BZOJ5003【与链】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

有权值为 $0\sim n$ 的 $n+1$ 个点,如果 $u\ and\ v=v$ 那么 $u$ 有一条到 $v$ 的有向边,现在问点数为 $k$ ,且权值加和为 $n$ 的路径条数(可以重复走,点数和权值重复计算)。

解题报告

我怎么啥都不会啊,看到 $u\ and\ v=v$ 以为是真子集,想了很久才发现可以有自环……WTF……

直接做很难办,我们按照二进制考虑,会发现一条路径其实对应了一个数组 $a_x$ 表示路径上 $x$ 这个二进制位出现了多少次,且 $0\le a_x\le k,\sum a_x2^x=n$ 。

于是变成了个背包……$f[i][j]$ 表示前 $i$ 个二进制位用了 $j$ 这么多体积的方案数,转移需要前缀和优化。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100000,Log=17,MOD=1e9+9;

int n,Lg,K,f[Log+5][maxn+5];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&K,&n);while ((1<<Lg)<n) Lg++;
    for (int j=0;j<=K&&j<=n;j++) f[0][j]=1;
    for (int i=1;i<=Lg;i++){
        for (int j=0;j<(1<<i)&&j<=n;j++) f[i][j]=f[i-1][j];
        for (int j=1<<i;j<=n;j++){
            AMOD(f[i][j]=f[i][j-(1<<i)],f[i-1][j]);
            if (j>=(LL)(K+1)*(1<<i)) AMOD(f[i][j],MOD-f[i-1][j-(K+1)*(1<<i)]);
        }
    }return printf("%d\n",f[Lg][n]),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up