2^k进制数

2^k进制数

题目链接:https://www.luogu.org/problem/show?pid=1066

题目大意&分析

​ 把每一位看作是一个序列中的数,则总共有W/K或W/K+1个数:

  1. W%K==0 (W/K)

    可以看到,此时变成了求给定全集中不重子序列数量,考虑组合数公式,使用高精的杨辉三角推得结果.

  2. W%K!=0 (W/K+1)

    枚举第一位(有位数限制),因为这是一个升序排列,所以后方元素会受到限制,即给定全集不同,其余同上.

代码
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
进制数
Luogu P1066
AC
*/
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int K,W;
int yh[520][520][60];//万进制
const int lendit=58;
int ans[60];
int t[60];
// code
void initNum(int *a)
{
    a[lendit]=1;
}
void display(int *a)
{
    printf("%d",a[a[lendit]-1]);
    for(int i=a[lendit]-2; i>=0; --i)
    {
        printf("%04d",a[i]);
    }
    printf(" ");
}
void add(int *a,int *b,int *out)//万进制高精
{
    int len=max(max(out[lendit],a[lendit]),b[lendit]);
    out[lendit]=len;
    for(int i=0; i<len; ++i)
    {
        out[i]+=(a[i]+b[i]);
        if(out[i]>=10000)
        {
            int t=out[i]/10000;
            out[i]%=10000;
            out[i+1]+=t;
        }
    }
    if(out[out[lendit]]!=0) ++out[lendit];
}
void init()
{
    scanf("%d%d",&K,&W);
    for(int i=0; i<=(1<<K)+4; ++i)
        for(int j=0; j<=(1<<K)+4; ++j)
            initNum(yh[i][j]);
    initNum(t);
    initNum(ans);
    yh[1][1][0]=1;
    for(int i=2; i<=(1<<K)+4; ++i)
        for(int j=1; j<=i; ++j)
            add(yh[i-1][j-1],yh[i-1][j],yh[i][j]);
}
void work()
{
    for(int i=2; i*K<=W; ++i)
        if(((1<<K)-1)>=i)
            add(t,yh[(1<<K)+1-1][i+1],ans);
    int hdit=(1<<(W%K));
    for(int i=1; i<hdit; ++i)
        if(((1<<K)-1-i)>=(W/K))
            add(t,yh[(1<<K)-1-i  +1][W/K+1],ans);
    display(ans);
}
int main()
{
    init();
    work();
    return 0;
}