考试题 codevs 5251 WYW的数字金字塔

*PS：原来暴力优化优化是可以过的么qwq，ljoj 数据手动测并没有T。。。最后默默的吐槽一句，附上一个金字塔的图是因为怕我们没有见过吗。。。

go to the problem

题目描述 Description

wyw有一个数字n，他要用这个数字写出一个数字金字塔。

wyw用随机数生成器生成了一个小于n且大于1的正整数k。

wyw找来一张白纸，他在白纸的最低端写下了这个数字n。

wyw在n的上面紧挨着写下了一个正整数a1，a1满足不大于n/k，

wyw又在a1上面写下了一个正整数a2，满足a2不大于a1/k，

时间过了t…

wyw在ah-1的上面写下了一个正整数ah，满足ah不大于ah-1/k

wyw已经无法在ah的上方写出不大于ah/k的数字了

这时，wyw就已经写好了一个高度为h（这里应该为h+1）的数字金字塔

wyw可以按照这个规则写出好多符合条件的数字金字塔。

试问：wyw一共能够写出多少种数字金字塔？wyw能写出的所有的数字金字塔中最高的金字塔的高度是多少？

注意：由于答案可能较大，所以对每一组数据请输出答案对p取模后的值。

输入描述 Input Description

输入数据的第一行包含两个正整数T、p，表示有T组测试数据，p的意义如题目所述

后面跟着T组数据，每组数据仅一行，包含了一个正整数n和k，意义如题目所述

输出描述 Output Description

输出数据一共n行，每行两个整数，表示答案对p取模后的值

样例输入 Sample Input

2 2

6 2

20 3

样例说明：以20 3这组数据为例，wyw能写出的所有金字塔如下

样例输出 Sample Output

1 1

1 1

数据范围及提示 Data Size & Hint

Solution 1 暴力

（codevs 上会T3个点，但手动测了测根本就没T 。。。qwq）

代码

#include
#include
#include
#include
#include
using namespace std;long long T,k;
long long n=0,p,cnt;
int f[50000010];int main()
{scanf("%lld%lld",&T,&p);while(T--){scanf("%lld%lld",&n,&k);int z=n/k;f[0]=0;for(int i=1;i<=2*k-1;++i) f[i]=1;  // 2*k之前都只能放一个，只有一种方案。for(int i=2*k;i<=z+1;++i) f[i]=0;for(int i=2*k;i<=z;++i)  // 递推for(int j=i/k;j>=1;--j) f[i]=(f[i]%p+f[j]%p)%p;for(int i=1;i<=z;++i) f[0]=(f[0]%p+f[i]%p)%p; //用0存防止爆空间if(!f[0]) ++f[0]; // 只能放n也是一种方案printf("%lld ",f[0]%p);cnt=1;while(n/k){n/=k;cnt=(cnt+1)%p;}printf("%lld\n",cnt);}return 0;
}

Solution 2 DP

代码

#include
#include
#include
#include
#include
using namespace std;long long T,P,n,k;
int S[500020];int main()
{scanf("%lld%lld",&T,&P);S[0]=S[1]=1;while(T--){scanf("%lld%lld",&n,&k);int N=n/k,ans2=1;for(int i=2;i<=N;++i)S[i]=(S[i-1]+S[i/k])%P;while(n/k) {n/=k;ans2=(ans2+1)%P;}printf("%d %lld\n",S[N],ans2);}return 0;
}
/*
用数组s[i]表示以不大于i为底的数字所达到的方案数之和。
F[i]表示以某一数字（i）为底的方案数。
而F[i]恰好为s[i/k].
所以方程式为：s[i] = s[i–1] + f[i];  （类似前缀和）PS：这里直接把f换成了s
*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！