这题是一个背包问题 这样的 在一个k子树上 每个节点都有自己的k个孩子 然后 从原点走 走到 某个点的 和为 N 且每条的 长度不小于D 就暂停问这样的 路有多少条， 呵呵 想到了 这样做没有把他敲出来，可以很清楚的 到达第几层都能到达那些状态 然后 最多N层看看每层取到什么样的值 然后先算出没有任何限制 的路有多少条 接着用权值小于D的路径做看能够搞多少条 然后相减一下就好了
#include <cstdio> #include <string.h> #include <iostream> using namespace std; const int MOD =1000000007; int dp[2][110],N,M,D; int main(){ while(scanf("%d%d%d",&N,&M,&D) == 3){ memset(dp,0,sizeof(dp)); int ans = 0 , dec = 0 , t=0; dp[0][0] = 1; for( int i =1 ; i <= N ; i++){ t=t^1; memset(dp[t],0,sizeof(dp[t])); for( int j =1 ;j <=M ; ++ j ) for( int k = j ; k <= N ; k ++ ){ dp[t][k] = (dp[t][k]+dp[1^t][k-j])%MOD; } ans=(ans+dp[t][N])%MOD; } t = 0 ; memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1 ;i <= N ; ++ i){ t= t^1; memset(dp[t],0,sizeof(dp[t])); for( int j = 1 ; j < D ; j ++) for( int k=j ; k <=N ; k++) dp[t][k]=(dp[t][k]+dp[t^1][k-j])%MOD; dec=(dec+dp[t][N])%MOD; } printf("%d ",(ans-dec+MOD)%MOD); } return 0; }
D 这题说的是 找出 n 使得 在n+1 n+2 。。。n*2 的所有的 数中 准确的找出 有m个 数具有准确的 k个1（在二进制当中） 事先得证明这样的一点就是 n + 2 ... 2·(n + 1) at least counts of such numbers on segment n + 1 ... 2·n 是正确的 因为这样如果一个数 可以通过排列组合证明 越大的 n的 k个1的个数都是大于等于小于n的数，我们可以猜猜这个是怎么来的，这样如果形成了一个数n 那么从0 到n当中的k个1 的个数小于等于 从0 到 n + 1 然后 同样的 n * 2 得到的个数小于等于 （ n + 1 ） * 2 那就要算 F[n*2] -F[n] < F[(n+1)*2] -F[n+1]; 可以通过组合去计算大小 也可以 这样 想 后者的区间在不断的 夸大 他所能到达的个数比前一个区间来的大
#include <string.h> #include <cstdio> #include <iostream> using namespace std; const int maxn = 65; const __int64 inf=2000000000000000000LL; #define bit(mask,i)((mask>>i)&1) int count( __int64 num){ int ans = 0 ; for( ; num ; num=num&(num-1)) ans ++; return ans; } __int64 dp[maxn][maxn] ,m; __int64 solve(__int64 X,int num){ __int64 ans = num==count(X); for( int i=63 ; i >=0 && num>=0 ; i--) if(bit(X,i)) ans+=dp[i][num--]; return ans; } int main(){ int k; memset(dp,0,sizeof(dp)); dp[0][0]=1; for( int i = 1 ; i<=64 ; ++ i ) for( int j = 0 ; j <= i ; ++ j ) dp[i][j]=dp[i-1][j]+(j?dp[i-1][j-1]:0); scanf("%I64d%d",&m,&k); __int64 L=1 ,R=inf/2 ,mid ; while(L<R){ mid = L + (R-L)/2; if(solve(mid*2,k)-solve(mid,k)<m ) L = mid+1; else R=mid; } printf("%I64d ",L); return 0; }