题目概述

有权值为 $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;
}