codeforces 247 div.2

本文从WordPress迁移而来, 查看全部WordPress迁移文章

C.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 110
#define MOD 1000000007
#define LL long long

LL dp[N][N][2];
int n,kth,d;

int main(){
while(scanf("%d%d%d",&n,&kth,&d)!=EOF){
memset(dp,0,sizeof(dp));
for(int i = 1; i <= kth; i++){
if(i >= d) dp[1][i][1] = 1LL;
else dp[1][i][0] = 1LL;
}
for(int lev = 2; lev <= 100; lev++){
for(int val = 0; val <= n; val++){
for(int w = 1; w <= kth && val+w<=n; w++){
dp[lev][val+w][1] += dp[lev-1][val][1];
dp[lev][val+w][1] %= MOD;
if(w >= d){
dp[lev][val+w][1] += dp[lev-1][val][0];
dp[lev][val+w][1] %= MOD;
}
else{
dp[lev][val+w][0] += dp[lev-1][val][0];
dp[lev][val+w][0] %= MOD;
}
}
}
}
LL sum = 0LL;
for(int lev = 1; lev <= 100; lev++)
sum = (sum + dp[lev][n][1]) % MOD;
cout << sum << endl;
}
return 0;
}

D.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
题意:给定m,k,找到任意一个n,满足[n+1,2*n]这些数当中,恰好有m个数字的
二进制表示中恰好有k个1
猜想,如果k一定的话,应该n越大,[n+1,2*n]当中会有越多的数字的二进制中有
恰好k个1
暴力验证后,发现是的
所以可以二分枚举n
现在问题剩下:对于一个n,怎么计算出[n+1,2*n]中有多少个数字,其二进制表示
中恰好有k个1
res = solve(2*n) - solve(n) //计算0到2n的个数 - 0到n的个数
现在问题又变为怎么计算 solve(x)
对于一个数字x,用二进制去表示它
方法是构造,保证构造的数字时刻 z <= x
1.如果x的当前位是1,我们在构造的数字里面填0的话,那么后面的位数爱怎么填就
怎么填,看看z之前已经用了多少个1,那么就是在剩下的位里面填剩下的1,其余填
0,这是个组合数
2.如果当前位是0,那么z只能填0

如果x本身刚好就是有k个1的话,最后加1,因为这样的计算方法,会漏掉1个
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
#define MAX 1000000000000000000LL
#define MAXBIT 64

LL C[MAXBIT+10][MAXBIT+10];

void init(){
for(int i = 0; i <= MAXBIT; i++) C[i][0] = 1LL;
for(int i = 1; i <= MAXBIT; i++)
for(int j = 1; j <= i; j++)
C[i][j] = C[i-1][j] + C[i-1][j-1];
}

LL solve(LL n,int K){
LL res = 0LL;
int one = 0;
for(int b = 62; b >= 0; b--){
if(n&(1LL<<b)){
if(K-one >= 0) res += C[b][K-one];
one++;
}
}
if(one == K) res++;
return res;
}

int main(){
init();
LL m; int K;
while(cin >> m >> K){
LL low = 1 , high = MAX , ans = -1LL;
while(low <= high){
LL mid = (low + high) >> 1LL;
LL res = solve(mid<<1LL,K) - solve(mid,K);
if(res == m) { ans = mid; break; }
else if(res < m) low = mid + 1LL;
else high = mid - 1LL;
}
cout << ans << endl;
}
return 0;
}