一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
lucas => 分解为k进制数 =>
一堆只包含若干小于k的数相乘的组合数相乘 mod k 为 0 =>
某个组合数或某些组合数 下 < 上 =>
求 0 <= i <= n 0 <= j <= m ，i的k进制中至少有一位小于j的k进制的（i，j）个数 =>
数位dp + 差分 =>
tot - i的k进制中每一位都大于等于j的k进制的每一位（i，j）个数
f[i][j]剩余i位，前缀状态为j的满足条件的数字数目
朴素数位dp O(k)状态转移，会TLE
改进为O(1)状态转移:根据可转移状态能得到能填数字的范围，计算出该范围内的数位对，乘法原理优化状态转移
f(n, pre)
前缀状态:
0 都未匹配
1 i和n前缀匹配
2 j和m前缀匹配
3 i和n前缀匹配 且 j和m前缀匹配
cnt0(x, y)：计算i in [0, x] j in [0, y]的符合条件(i, j)数目
cnt1(x, y) = min(x, y) + 1
cnt2(x, y) = x - y + 1
cnt3(x, y) = x >= y (bool)
状态转移：
f(n, 0) = f(n - 1, 0) * cnt0(k - 1, k - 1)
f(n, 1) = f(n - 1, 0) * cnt0(dn[n] - 1, k - 1) +
f(n - 1, 1) * cnt1(dn[n], k - 1)
f(n, 2) = f(n - 1, 0) * cnt0(k - 1, dm[n] - 1) +
f(n - 1, 2) * cnt2(k - 1, dm[n])
f(n, 3) = f(n - 1, 0) * cnt0(dn[n] - 1, dm[n] - 1) +
f(n - 1, 1) * cnt1(dn[n], dm[n] - 1) +
f(n - 1, 2) * cnt2(dn[n] - 1, dm[n]) +
f(n - 1, 3) * cnt3(dn[n], dm[n])
这道题有个很玄学的地方就是cnt0中x和y的取模如果放在第二if和第一个if之间就会WA6个点，但是if内写一个，if外写一个就不会，到底是什么原因呢？
----
2024.04.12
知道为什么了，后六个点1e18的数据量比1e9 + 7大，事实上需要取模的应该是return语句的操作数而非x，y，理论上先前的代码不对，现已更正
2、复杂度
时间复杂度： O(log_{k}^{n} * 4)空间复杂度：O(log_{k}^{n} * 4)
3、代码详解
#include <iostream>
#include <cstring>
#define int long long
using namespace std;
const int N = 65, mod = 1e9 + 7, inv2 = 500000004;
int f[N][4];
int k, dn[N], dm[N], lenn, lenm;
inline int cnt0(int x, int y)
{
if (x < 0 || y < 0)
return 0;
if (x < y)
{
return ((x + 2) % mod) * ((x + 1) % mod) % mod * inv2 % mod;
}
return (((y + 2) % mod) * ((y + 1) % mod) % mod * inv2 % mod + ((x - y) % mod) * ((y + 1) % mod) % mod) % mod;
}
inline int cnt1(int x, int y){
return (min(x, y) + 1) % mod;
}
inline int cnt2(int x, int y){
if(x < y) return 0;
return (x - y + 1) % mod;
}
inline int cnt3(int x, int y){
return x >= y;
}
int dfs(int n, int pre){
if(!n) return 1;
if(~f[n][pre]) return f[n][pre];
int& res = f[n][pre] = 0;
if(!pre)
res = dfs(n - 1, 0) * cnt0(k - 1, k - 1) % mod;
if(pre == 1)
res = (dfs(n - 1, 0) * cnt0(dn[n] - 1, k - 1) % mod +
dfs(n - 1, 1) * cnt1(dn[n], k - 1) % mod) % mod;
if(pre == 2)
res = (dfs(n - 1, 0) * cnt0(k - 1, dm[n] - 1) % mod +
dfs(n - 1, 2) * cnt2(k - 1, dm[n]) % mod) % mod;
if(pre == 3)
res = (dfs(n - 1, 0) * cnt0(dn[n] - 1, dm[n] - 1) % mod +
dfs(n - 1, 1) * cnt1(dn[n], dm[n] - 1) % mod +
dfs(n - 1, 2) * cnt2(dn[n] - 1, dm[n]) % mod +
dfs(n - 1, 3) * cnt3(dn[n], dm[n]) % mod) % mod;
return res %= mod;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _ = 1;
cin >> _ >> k;
while(_--){
memset(f, -1, sizeof f);
memset(dn, 0, sizeof dn), memset(dm, 0, sizeof dm);
int n, m;
cin >> n >> m;
m = min(n, m);
int tot = cnt0(n, m);
lenn = lenm = 0;
while(n) dn[++lenn] = n % k, n /= k;
while(m) dm[++lenm] = m % k, m /= k;
cout << ((tot - dfs(lenn, 3)) % mod + mod) % mod << '\n';
}
return 0;
}
/**
lucas => 分解为k进制数 =>
一堆只包含若干小于k的数相乘的组合数相乘 mod k 为 0 =>
某个组合数或某些组合数 下 < 上 =>
求 0 <= i <= n 0 <= j <= m ，i的k进制中至少有一位小于j的k进制的（i，j）个数 =>
数位dp + 差分 =>
tot - i的k进制中每一位都大于等于j的k进制的每一位（i，j）个数
f[i][j]剩余i位，前缀状态为j的满足条件的数字数目
朴素数位dp O(k)状态转移，会TLE
改进为O(1)状态转移:根据可转移状态能得到能填数字的范围，计算出该范围内的数位对，乘法原理优化状态转移
f(n, pre)
前缀状态:
0 都未匹配
1 i和n前缀匹配
2 j和m前缀匹配
3 i和n前缀匹配 且 j和m前缀匹配
cnt0(x, y)：计算i in [0, x] j in [0, y]的符合条件(i, j)数目
cnt1(x, y) = min(x, y) + 1
cnt2(x, y) = x - y + 1
cnt3(x, y) = x >= y (bool)
状态转移：
f(n, 0) = f(n - 1, 0) * cnt0(k - 1, k - 1)
f(n, 1) = f(n - 1, 0) * cnt0(dn[n] - 1, k - 1) +
f(n - 1, 1) * cnt1(dn[n], k - 1)
f(n, 2) = f(n - 1, 0) * cnt0(k - 1, dm[n] - 1) +
f(n - 1, 2) * cnt2(k - 1, dm[n])
f(n, 3) = f(n - 1, 0) * cnt0(dn[n] - 1, dm[n] - 1) +
f(n - 1, 1) * cnt1(dn[n], dm[n] - 1) +
f(n - 1, 2) * cnt2(dn[n] - 1, dm[n]) +
f(n - 1, 3) * cnt3(dn[n], dm[n])
**/
