背景
国王之手不喜欢巨人 ，巨人也不喜欢国王之手，但他们有一个共同点：都不喜欢炼金师。
——Deadcells:王座之间
题面
一个阶梯状图形，第一行靠右有
n
n
n 个色块，第二行靠右有
n
?
1
n-1
n?1 个色块……一直到第
n
n
n 行。令
f
(
n
)
f(n)
f(n) 等于用最少的矩形不重叠地刚好覆盖所有色块的方案数。
定义
V
(
x
)
V(x)
V(x) 为
x
x
x 的质因数分解中 7 的幂。
求
max
?
i
=
l
r
V
(
(
i
+
1
)
f
(
i
)
)
\max_{i=l}^r V((i+1)f(i))
maxi=lr?V((i+1)f(i)) 。
l
≤
r
≤
1
0
10000
l\leq r\leq 10^{10000}
l≤r≤1010000 。
题解
这道题，懒人是很难做出来的。
我们先分析函数
f
(
n
)
f(n)
f(n) ，容易发现
f
(
n
)
f(n)
f(n) 的递推式：
f
(
n
)
=
∑
i
=
1
n
f
(
i
?
1
)
f
(
n
?
i
)
f(n)=\sum_{i=1}^{n} f(i-1)f(n-i)
f(n)=i=1∑n?f(i?1)f(n?i)
这个递推式和卡塔兰数的递推式一模一样，由于开头的几项也一样，所以
f
(
n
)
f(n)
f(n) 就是卡塔兰数。
如果我们列出卡塔兰数的这个表达式
f
(
n
)
=
(
2
n
n
)
?
(
2
n
n
?
1
)
f(n)={2n\choose n}-{2n\choose n-1}
f(n)=(n2n?)?(n?12n?) ，我们是做不出来的。所以记忆不同的一些表达式总是很有必要：
f
(
n
)
=
(
2
n
n
)
?
(
2
n
n
?
1
)
=
(
2
n
n
)
?
n
n
+
1
?
(
2
n
n
)
=
(
2
n
n
)
n
+
1
f(n)={2n\choose n}-{2n\choose n-1}={2n\choose n}-\frac{n}{n+1}\cdot {2n\choose n} =\frac{2n\choose n}{n+1}
f(n)=(n2n?)?(n?12n?)=(n2n?)?n+1n??(n2n?)=n+1(n2n?)?
代进去，刚好
max
?
i
=
l
r
V
(
(
i
+
1
)
f
(
i
)
)
=
?
max
?
i
=
l
r
V
(
(
2
i
i
)
)
=
max
?
i
=
l
r
V
(
(
2
i
)
!
)
?
2
V
(
i
!
)
\max_{i=l}^r V((i+1)f(i))=\\~\\ \max_{i=l}^r V\left({2i\choose i}\right)= \\\max_{i=l}^r V((2i)!)-2V(i!)
i=lmaxr?V((i+1)f(i))=?i=lmaxr?V((i2i?))=i=lmaxr?V((2i)!)?2V(i!)
接下来冷静分析
V
(
x
!
)
V(x!)
V(x!)：
V
(
x
!
)
=
∑
i
=
1
?
x
7
i
?
V(x!)=\sum_{i=1} \left\lfloor \frac{x}{7^i} \right\rfloor
V(x!)=i=1∑??7ix??
我们把
x
x
x 表示成
7
7
7 进制数
∑
i
=
0
a
i
7
i
\sum_{i=0} a_i7^i
∑i=0?ai?7i 就好办了
V
(
x
!
)
=
∑
i
=
0
a
i
7
i
?
1
?
1
6
=
∑
i
=
0
(
a
i
7
i
?
1
?
a
i
)
6
=
?
x
/
6
?
?
∑
i
=
0
a
i
6
V(x!)=\sum_{i=0} a_i\frac{7^{i-1}-1}{6}=\frac{\sum_{i=0} (a_i7^{i-1}-a_i)}{6}=\frac{\lfloor x/6\rfloor-\sum_{i=0}a_i}{6}
V(x!)=i=0∑?ai?67i?1?1?=6∑i=0?(ai?7i?1?ai?)?=6?x/6??∑i=0?ai??
我们再令
S
x
=
∑
i
=
0
a
i
S_x=\sum_{i=0}a_i
Sx?=∑i=0?ai? ，答案式子就很直观了
max
?
i
=
l
r
V
(
(
2
i
)
!
)
?
2
V
(
i
!
)
=
max
?
i
=
l
r
2
S
i
?
S
2
i
6
\max_{i=l}^r V((2i)!)-2V(i!)=\max_{i=l}^r \frac{2S_i-S_{2i}}{6}
i=lmaxr?V((2i)!)?2V(i!)=i=lmaxr?62Si??S2i??
由于
S
i
S_i
Si? 是七进制下每一位的和，所以最终答案不超过两万！
最后我们可以用数位DP来解决，除了是否抵达上/下界，还要记录
2
i
2i
2i 后续是否进位，不然无法处理
S
2
i
S_{2i}
S2i? 。
由于需要进制转换，所以用压位高精的话，时间是极小常数的
O
(
∣
r
∣
2
)
O(|r|^2)
O(∣r∣2) 。
CODE
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 10005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
int xchar() {
static const int maxn = 1000000;
static char b[maxn];
static int pos = 0,len = 0;
if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
if(pos == len) return -1;
return b[pos ++];
}
LL read() {
LL f = 1,x = 0;int s = getchar();
while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}
return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {
if(!x) {putchar('0');return ;}
if(x<0) putchar('-'),x = -x;
return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}
int n,m,s,o,k;
char ll[MAXN],rr[MAXN];
const int B = 100000000;
struct it{
vector<int> s;
int n;
it(){s.resize(2); s[n=1] = 0;}
it(int x){s.resize(2); s[n=1] = x;}
int MD(int x) {
int as = 0;
for(int i = n;i > 0;i --) {
as = (as*B%x + s[i]) % x;
}return as;
}
bool emp() {return n == 1 && s[1] == 0;}
};
it operator + (it a,it b) {
int m = 0;
for(int i = 1;i <= a.n || i <= b.n || m;i ++) {
if(i >= a.s.size()) a.s.push_back(0);
if(i > a.n) a.s[++ a.n] = 0;
if(i >= b.s.size()) b.s.push_back(0);
if(i > b.n) b.s[++ b.n] = 0;
a.s[i] = a.s[i] + b.s[i] + m;
if(a.s[i] > B) a.s[i] -= B,m = 1;
}
return a;
}
it operator * (it a,it b) {
it c; if(a.n > b.n) swap(a,b);
for(int i = 1;i <= a.n;i ++) {
int m = 0;
for(int j = 1;j <= b.n || m;j ++) {
if(j >= b.s.size()) b.s.push_back(0);
if(j > b.n) b.s[++ b.n] = 0;
if(i+j-1 >= c.s.size()) c.s.push_back(0);
if(i+j-1 > c.n) c.s[++ c.n] = 0;
LL nm = (c.s[i+j-1] + a.s[i]*1ll*b.s[j] + m);
m = nm/B; c.s[i+j-1] = nm%B;
}
}return c;
}
it operator / (it a,int b) {
LL m = 0;
for(int i = a.n;i > 0;i --) {
m = m*B + a.s[i];
a.s[i] = m / b; m %= b;
} while(a.n > 1 && a.s[a.n] == 0) a.n --;
return a;
}
int a[MAXN<<2],b[MAXN<<2];
int dp[MAXN<<2][2][2][2];
int main() {
freopen("dingdingcar.in","r",stdin);
freopen("dingdingcar.out","w",stdout);
it L,R;
scanf("%s",ll + 1);
n = strlen(ll + 1);
scanf("%s",rr + 1);
m = strlen(rr + 1);
for(int i = 1;i <= n;i ++) L = L * it(10) + it(ll[i]-'0');
for(int i = 1;i <= m;i ++) R = R * it(10) + it(rr[i]-'0');
n = 0; m = 0;
while(!L.emp()) a[++ n] = L.MD(7),L = L/7;
while(!R.emp()) b[++ m] = R.MD(7),R = R/7;
int le = max(n,m);
for(int s = 0;s < 2;s ++) {
for(int o = 0;o < 2;o ++) {
for(int k = 0;k < 2;k ++) {
dp[le+2][s][o][k] = -0x3f3f3f3f;
}
}
}
dp[le+2][0][0][0] = 0;
for(int i = le+1;i > 0;i --) {
for(int s = 0;s < 2;s ++) {
for(int o = 0;o < 2;o ++) {
for(int k = 0;k < 2;k ++) {
dp[i][s][o][k] = -0x3f3f3f3f;
}
}
}
for(int s = 0;s < 2;s ++) {
for(int o = 0;o < 2;o ++) {
int nl = (s ? 0:a[i]),nr = (o ? 6:b[i]);
for(int x = nl;x <= nr;x ++) {
bool k1 = ((x<<1)>=7 ? 1:0),k2 = ((x<<1|1)>=7 ? 1:0);
bool A = (s || x > a[i]),B = (o || x < b[i]);
dp[i][A][B][0] = max(dp[i][A][B][0],dp[i+1][s][o][k1] + x*2 - (x*2%7));
dp[i][A][B][1] = max(dp[i][A][B][1],dp[i+1][s][o][k2] + x*2 - ((x<<1|1)%7));
}
}
}
}
int ans = 0;
for(int s = 0;s < 2;s ++) {
for(int o = 0;o < 2;o ++) {
ans = max(ans,dp[1][s][o][0]);
}
}
ans /= 6;
AIput(ans,'\n');
return 0;
}
|