大力猜结论竟然猜对了。。
对于一对$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;
}
```