参考题解
• 首先我们定义一个表pri[max],pri[i]表示第i个质数， 第一个质数为2.设数组max，其中max[i]记录i的最 大质因子。定义f(b,x1,x2)表示区间[x1,x2]之间不包 括大于第b个质数的质因子的所有正整数，则有如 下递归关系： F(b,x1,x2)=f(b-1,x1,x2)+f(b,(x1-1) div pri[b]+1,x2 div pri[b]) • 该递归式的边界条件为： • F=0 x1>x2 • F=x2-x1+1 x2<=pri[b] • 可直接验证 x1=x2 • F=trunc(log2(x2))-trunc(log2(x1)) b=1
例3：出栈序列统计
• 【问题描述】 • 栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进 栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种： push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。 现在要使用这两种操作，由一个操作序列可以得到一系列的输出 序列。请你编程求出对于给定的n，计算并输出由操作数序列1 ，2，…，n，经过一系列操作可能得到的输出序列总数。 • 【输入】 【输出】 • 就一个数n(1≤n≤1000)。 一个数，即可能输出序列的总数目。 • 【样例】 • stack.in stack.out • 3 5
• 答案为f[n]，时间复杂度为O(n)。
方法二
• 对于i>=3,分析第一列的两个格子覆盖情况，有两种情 况： 1.用1*2的骨牌竖着覆盖第一列，这种情况的方案数等 于后面2*(i-1)的长方形的覆盖方案数，即f[i-1]；
2.用两个1*2的骨牌横着覆盖，这种情况的方案数等于 后面2*(i-2)的长方形的覆盖方案数，即f[i-2]。
【算法分析】
• C(2n,n)/(n+1) • =2n*(2n-1)*(2n-2)…*(n+1)/n!/(n+1) • =2n*(2n-1)*(2n-2)*…*(n+2)/n!。 • 考虑到这个数据可能比较大，所以用高精度 运算来计算这个结果。 • 本题实际是一个经典的Catalan数模型。有关 Catalan数的详细解释请参考《组合数学》等书 。
方法二
• 当k达到106的时候，方法一会超时。 • 由于10007是素数，在计算C(k,n)mod 10007时可以采用扩展GCD来解决。 • 时间复杂度为O(k)。
参考代码：
#include <iostream> #include <fstream> using namespace std; ifstream fin("factor.in"); ofstream fout("factor.out"); const int MAXN=1005; int dp[MAXN][MAXN],a,b,k,n,m,ans;
例2：B光滑数
• 【问题描述】 • B为一个正整数，如果一个自然数N的质因子分解式中没有大于B的因子， 我们就称N是一个B光滑数。请你编一个程序，求出某个区间中所有的B光 滑数的个数。 • 输入： • 输入文件名为bnum.in，仅有一行，包含三个用空格隔开的整数N,M,B,其 中1<=N<=2，000，000，000,1<=M<=100，000，000,1<=B<=1，000 ，000。 • 输出：输出文件名为bnum.out，仅一行。一个整数，表示区间[N,N+M]之 间的B光滑数的个数。 • 【样例输入】 • 30 10 5 • 【样例输出】 • 4
【思考与提高】
【思考与提高】
再设f(a,b)为从状态(a,b)通过移动火车变为状态(0,0) 的所有移动方法。类似于动态规划的状态转移方程，我 们可写出以下递归式：
边界值：f(0,0)=1。 有了这个递归公式后，再写程序就比较简单了。
例4：骨牌覆盖问题
• 有2行n列的长方形方格，要求用n个1*2的 骨牌铺满。有多少种铺法？ • 如n=3时有以下3种覆盖方法：
递推算法
确定状态 确定递推关系和边界条件
day2)
• 【题目描述】给定一个多项式(ax+by)k,请求出多项式展 开后xnym项的系数 • 【输入】共一行，包含5个整数，分别为a,b,k,n,m，每 两个整数之间用一个空格隔开。 • 【输出】输出共1行，包含一个整数，表示所求的系数 ，这个系数可能很大，输出对10007 取模后的结果。 • 【输入输出样例】 factor.in factor.out 11312 3 • 【数据范围】 对于 30%的数据，有0≤k≤10； 对于 50%的数据，有a = 1，b = 1； 对于 100%的数据，有0≤k≤1,000，0≤n, m≤k， 且n + m = k，0≤a，b≤1,000,000。
int main() { fin>>a>>b>>k>>n>>m;
dp[1][1]=dp[1][2]=1; for (int i=2;i<=k;i++) for (int j=1;j<=i+1;j++) dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % 10007; ans = dp[k][m+1];
【思考与提高】
我们知道，在某个状态下，所能做的操作(移动方法)无非 有两种： （1）将右方的等待进栈的第一个元素进栈； （2） 将栈顶的元素出栈，进入左边的出栈序列。 设此时右方、栈、左方的元素个数分别为a，b，c。我 们就能用(a,b,c)表示出当前的状态。显然n=a+b+c，则 c=n-a-b。即已知a和b，c就被确定，所以我们可以用(a,b) 来作为状态的表示方法。则起始状态为(n,0)，目标状态为 (0,0)。 又由上面的两种移动方法，我们可类似的得到两种状 态转移方式：
参考程序： #include <iostream>
#include <cstdio> using namespace std; typedef long long lld; lld i,n,ans; lld h[1000]; int main() { freopen ("stack.in","r",stdin); freopen ("stack.out","w",stdout); h[2]=1; cin>>n; n=n+2; for (lld i=3;i<=n;i++) for (lld k=2;k<i;k++) h[i]=h[i]+h[k]*h[i-k+1]; cout<<h[n]<<endl; return 0; }
方法一
• 状态：f[i]表示铺满2*i的长方形的方案数 • 找规律,手工或搜索求出i=1,2,3,4,5的方案数 分别为1，2，3，5，8,容易发现 f[i]=f[i-1]+f[i-2](i>=3) • 边界条件：f[1]=1,f[2]=2 • 递推关系式 • 1 i=1 • f[i]= 2 i=2 f[i-1]+f[i-2] i>=3
方法一
• 根据二项式定理可知： k k i k i k i i i i k i i k * * * * *x * y C (ax+by) = = k (ax) (by) C k a b i 0 i 0 n n m n m • 取i=n,x y 的系数为 C k * a * b • 其中an和bm可以用快速幂来计算，在lg(n)+lg(m)内完成。 n • 计算 C k 可以用递推来求解。 • 状态：f[i,j]表示从i个数中选j个数的方案数。f[k,n]就是答案。 • 根据第i数选还是不选来进行分析： 1.选择第i个数：此情况的方案数等价于从i-1个数中选择j-1个 数的方案数即f[i-1,j-1]; 2.不选第i个数：此情况的方案数等价于从i-1个数中选择j个数 的方案数即f[i-1,j] 所以f[i,j]=f[i-1,j-1]+f[i-1,j] • 边界条件：f[i,0]=1,f[i,i]=1。 时间复杂度为O(n*k)。
方法四
• 分治，一分为二来考虑,左边为n div 2列， 右边为n-n div 2列，如果左右独立则方案数 为f[n div 2]*f[n-n div 2],如果有横向覆盖第n div 2列和第n div 2+1列，则方案数为f[n div 2-1]*f[n-n div 2-1] • 所以f[n]= f[n div 2]*f[n-n div 2]+f[n div 21]*f[n-n div 2-1]
所以f[i]=f[i-1]+f[i-2]
方法三
• 分析用1*2的骨牌覆盖列的位置来计算方案数 • 1.如果i为偶数，覆盖方案分为两类： (1)没有竖立覆盖其中一列的情况：全部用横向覆盖的方 案，方案数为1； (2)有竖立覆盖的情况：为了避免重复，考虑第一次竖立 覆盖的位置在x列，x必须是奇数，而且前1到x-1列覆盖方 法唯一，全部采用横向覆盖，方案数等于后面i-x列的覆盖 情况，即f[i-x]。 • 所以当i为偶数时,f[i]=1+f[1]+f[3]+...+f[i-3]+f[i-1] • 2.如果i是奇数，一定有竖立覆盖的情况， f[i]=1+f[2]+f[4]+.....+f[i-3]+f[i-1] • 如何证明该递推关系式等价于f[i]=f[i-1]+f[i-2]？ • 试着用横向覆盖的来分析递推关系式。
【算法分析】
• 我们通过回溯的方法计算并输出不同的出栈序列，这里只 要求输出不同的出栈序列总数目，所以我们希望能找出相 应的递推公式进行处理。 • 从排列组合的数学知识可以对此类问题加以解决。 • 我们先对n个元素在出栈前可能的位置进行分析，它们 有n个等待进栈的位置，全部进栈后在栈里也占n个位置， 也就是说n个元素在出栈前最多可能分布在2*n位置上。 • 出栈序列其实是从这2n个位置上选择n个位置进行组合 ，根据组合的原理，从2n个位置选n个，有C(2n,n)个。但 是这里不同的是有许多情况是重复的，每次始终有n个连 续的空位置，n个连续的空位置在2n个位置里有n+1种， 所以重复了n+1次。所以出栈序列的种类数目为：