题解 P1066 【2^k进制数】

Iowa_BattleShip

2018-10-31 13:44:51

Solution

大力猜结论竟然猜对了。。 对于一对$k,w$,我们可以把$w$位划分成$k$位一段的形式,每一段就是转换成十进制后的一位,这个从题面的解释中应该可以理解。 先不考虑可能多出(即剩余不足以划成$k$位)的一段,这样使得每一位的枚举上界都是$2 ^ k - 1$,然后我们枚举几位数。 - $2$位数 十位为$1$,显然个位只能为$2\sim 2 ^ k - 1$,共$2 ^ k - 2$种。 十位为$2$,显然个位只能为$3\sim 2 ^ k - 2$,共$2 ^ k - 3$种。 $\dots$ 这么递推下去,在$2$位数的情况下,共$\sum \limits _{i = 1} ^ {2 ^ k - 2}i$种。 - $3$位数 百位为$1$,显然十位只能为$2\sim 2 ^ k - 2$,这时我们考虑去取之前计算$2$位数得到的结果,因为十位从$2$开始,所以共$\sum \limits _{i = 1} ^ {2 ^ k - 3}i$种。 百位为$2$,显然十位只能为$3\sim 2 ^ k - 2$,共$\sum \limits _{i = 1} ^ {2 ^ k - 4}i$种。 $\dots$ 递推下去,在$3$位数的情况下,共$\sum \limits _{i = 1} ^ {2 ^ k - 3} \sum \limits _{j = 1} ^ i j$种。 - $4$位数 同样如上考虑,共$\sum \limits _{i = 1} ^ {2 ^ k - 4} \sum \limits _{j = 1} ^ i \sum \limits _{k = 1} ^ {j} k$种。 $\dots$ 而这个一堆$\sum$的式子其实就相当于每次进行前缀和操作,于是我们就可以依照上面的模式递推下去了。 初始化$i = 1 \to 2 ^ k - 1,S[i] = i$。 枚举位数,再枚举首位(注意上界,要保证后面每一位都能填数),累计贡献,然后对$S$数组进行前缀和操作即可。 然后考虑不能划分成$k$位的那一段,其实只需单独拎出来进行单独枚举计算贡献即可(其实只是改个上界而已)。 因为数据较大,所以要用高精。 我的高精是直接$copy$我的[高精模板](https://www.cnblogs.com/Iowa-Battleship/p/9869499.html)~~(太懒了~~ 部分细节可看代码。 ```cpp #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int N = 210; const int M = 520; const int base = 1e8; struct bigint {//高精模板 int s[N], l; void CL(){ l = 0; memset(s, 0, sizeof(s)); } void pr() { printf("%d", s[l]); for (int i = l - 1; i; i--) printf("%08d", s[i]); } ll toint() { ll x = 0; for (int i = l; i; i--) x = x * base + s[i]; return x; } bigint operator = (int b) { CL(); do { s[++l] = b % base; b /= base; } while (b > 0); return *this; } bigint operator + (const ll &b) { bigint c = *this; ll x = b; for (int i = 1; i <= l && x; i++) { x = x + c.s[i]; c.s[i] = x % base; x /= base; } if (x) c.s[++c.l] = x; return c; } bigint operator + (bigint &b) { if (b.l < 3) return *this + b.toint(); bigint c; ll x = 0; int k = l < b.l ? b.l : l; c.CL(); c.l = k; for (int i = 1; i <= k; i++) { x = x + s[i] + b.s[i]; c.s[i] = x % base; x /= base; } if (x) c.s[++c.l] = x; return c; } };//以上都是高精模板 bigint s, S[M]; inline int re() { int x = 0; char c = getchar(); bool p = 0; for (; c < '0' || c > '9'; c = getchar()) p |= c == '-'; for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0'; return p ? -x : x; } int main() { int i, j, k, w, n, o; k = re(); w = re(); o = 1 << k; n = w / k + (w % k ? 1 : 0);//划分段数 w = w % k ? (1 << (w % k)) - 1 : o - n;//计算多出一段的上界,如果没有多出,那上界就是2 ^ k - n,因为要保证后面每一位都能填数。 if (n > o - 1)//若划分出来的段数多于2 ^ k - 1段,这多余的就是没有用的 { n = o - 1; w = o - n; } for (i = 1; i < o; i++)//初始化 S[i] = i; for (s = 0, i = 2; i <= n; i++)//枚举位数 { if (i < n) for (j = 1; j <= o - i; j++)//枚举首位填什么数,上界为2 ^ k - i s = s + S[o - i - j + 1];//后一位能填j + 1 ~ (2 ^ k - 1) - (i - 1),共2 ^ k - i - j + 1种 else//特判最后一段,改上界 for (j = 1; j <= w; j++) s = s + S[o - i - j + 1]; for (j = 1; j <= o - i; j++)//计算前缀和 S[j] = S[j] + S[j - 1]; } s.pr(); return 0; } ```