`
文章列表
莫比乌斯函数完整定义的通俗表达: 1)莫比乌斯函数μ(n)的定义域是N 2)μ(1)=1 3)当n存在平方因子时,μ(n)=0 4)当n是素数或奇数个不同素数之积时,μ(n)=-1 5)当n是偶数个不同素数之积时,μ(n)=1 /* * [题意] * 给出n, m, p,求有多少对a, b满足gcd(a, b)的素因子个数<=p * (其中1<=a<=n, 1<=b<=m) * * [解法] * 设A(d):gcd(a, b)=d的有多少种 * 设B(j): gcd(a, b)是j的倍数的有多少种,易知B(j) = (n/j ...
/* * [题意] * 有n个格子需要填色,有6种颜色(设为123456),要求: * 1、填完后要对称 * 2、相邻不能同色 * 3、不可出现123456的情况 * [解题方法] * 由于是对称所以只要处理前(n+1)/2个,翻过去即可(注意此时不可出现654321,因为要翻过去) * 即令n=(n+1)/2求解即可 *!设f(n,x):长度为n的以x结尾的合法颜色串个数 * 所以由题意得: * 1、f(n,1) = f(n-1,2)+f(n-1,3)+f(n-1,4)+f(n-1,5)+f(n-1, ...
/* * [题意] * 输入n, x, m * 求(1^x)*(x^1)+(2^x)*(x^2)+(3^x)*(x^3)+...+(n^x)*(x^n) * [解题方法] * 设f[n] = [x^n, n*(x^n), (n^2)*(x^n),..., (n^x)*(x^n)] * 则f[n][k] = (n^k)*(x^n) * 问题转化为求:( g[n] = f[1][x]+f[2][x]+...+f[n][x] ) * 设C(i,j)为组合数,即i种元素取j种的方法数 * 所以有:f[n+1][k] = ((n+1)^k)*(x^(n+ ...
/* * [题意] * 给出第一天是星期几,给出n,k * 第i天记忆的单词数是(i^k),其中特殊地:星期六、日记忆的单词数为0 * 问这n天一共记忆了多少个单词? * [解题方法] * 1、先说怎么求f[n][k] = (1^k)+(2^k)+(3^k)+...+(n^k) * 原式 = (0+1)^k + (1+1)^k + (2+1)^k +...+ ((n-1)+1)^k * 设:C(i,j)为组合数,i种元素取j种的方法数 * 由二次多项式得: * ((n-1)+1)^k = C(k,0 ...
/* * [题意] * 已知: * F(0)=1, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2) * A(0)=1, A(1)=1, A(n)=X*A(n-1)+Y*A(n-2) (n>=2) * 求:S(n), S(n) = (A(0)^2)+(A(1)^2)+...+(A(n)^2) * [解题方法] * (A(n)^2) = (X*A(n-1) + Y*A(n-2))^2 * = X*X*(A(n-1)^2) + Y*Y*(A(n-2)^2) + 2*X*Y*(A(n-1)*A ...
/* * [题意] * 略 * [解题方法] * 设g为所求。 * 观察可知:g(1) = a; g(2) = b; g(3) = a*b; g(4) = a*(b^2); g(5) = (a^2)*(b^3)... * 易得:g(n) = g(n-1)*g(n-2) * 所以对于a的幂或b的幂有:f(n) = f(n-1)+f(n-2) * 设矩阵A = |1 1| * |1 0| * 令B = A^(n-2),得: * g(n)中b的幂 = B[0][0]; * g(n)中a的幂 = B[0][1]; ...
/* * [题意] * F(0) = 0; F(1) = 1; F(n) = F(n-1)+F(n-2); (斐波那契数列) * 设C[i][j]为组合数i种元素中取j种元素的方法 * 给出n、m,求( C[n][0]*F(0)+C[n][1]*F(1)+...+C[n][k]*F(k) ) % m; * [解题方法] * 设矩阵 A = |1 1| * |1 0| * 设矩阵 B = (A^n) * 则B[0][0] = F(n-1); B[0][1] = B[1][0] = F(n); B[1][1] = F(n ...
/* * [题意] * 有k种珍珠,每种珍珠N个,问长度<=N且有k种珍珠的垂饰有多少个? * [解题方法] * dp[i][j]表示长度为i的并且有j种珍珠的垂饰有多少个 * 则有状态转移:dp[i][j] = (k-(j-1))*dp[i-1][j-1] + j*dp[i-1][j]; * 由于N太大,所以把i看成“阶段”,构造矩阵,通过矩阵快速转移 * 设第i阶段的一维数组(dp[i][0~j])状态设为F,转移矩阵为init(k+1阶方阵) * 则有:init * F = F';(F'为新状态) * 设答案 = gn = dp[1 ...
/* * [题意] * 有n个灯,初始时是全亮的,第一个灯可以按(按下之后改变状态) * 然后如果前k个灯全灭且第k+1个灯亮,则第k+2个灯可以按 * 问至少要多少步灭掉所有灯? * [解题方法](对于n个灯,所求为f[n]) * 1. 要想灭掉最后一个灯,得先灭掉前n-2个灯(第n-1个灯留亮)(f[n-2]+1) * {注:灭掉最后一个灯需要1步} * 2. 要想灭掉第n-1个灯,得先让第n-2个灯变回亮,要第n-2个灯变回亮,得先让第n-3个灯变回亮... * 即要把前n-2个灯都变回亮(f[n-2]) * 3. ...
/* * [题意] * 对于只由数字1和0构成的串 * 给出长度为n的, 不含子串101且不含子串111的串的个数(mod m) * [解题方法] * 设f[n]为长度是n的并且以0结尾的串的个数 * 设g[n]为长度是n的并且以1结尾的串的个数 * 则有: 1. f[n] = f[n-1](...00) + g[n-1](...10) * 2. g[n] = f[n-2](...001) + f[n-3](...0011) * 所以有矩阵: * |1 0 0 1| |f[n-1]| |f[n] ...
/* * [题意] * g(i) = k*i + b * f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2) * 已知k, b, n, M * 求( f(g(0))+f(g(1))+...+f(g(n-1)) ) % M * * [解题方法] * 设斐波那契矩阵A:{1, 1 * 1, 0} * 设B = (A^n) * 则有:B[0][0] = f(n+1), B[0][1] = B[1][0] = f(n), B[1][1] = f(n-1); * //上述为斐波那契矩阵的性质 ...
/* * [题意] * 给出n条道路,k个询问,每个询问包括起点v1、终点v2、t1天、t2天 * 问从v1到v2走了i天一共有多少走法(mod 2008)?(t1<=i<=t2) * [解题方法] * 设B = A^i; * 则A[u][v] 表示 从u到v走了i天(等价于走了i条边)的走法有多少 * 那么题目就转化为求:C = (A^t1+A^(t1+1)+...+A^t2) % 2008; * C[v1][v2]即为所求 */ #include <iostream> #include <stdio.h> ...
/* * [题意] * 将一个数拆成四个素数的和,若不可能,则输出"Impossible." * * [解题方法] * 根据哥德巴赫猜想,大于2的偶数能够分成两个素数的和 * (还没完全得到证明,但在题目所给范围内必然成立) * 利用这个猜想,只要根据输入的奇偶性,定死前两个素数 * 若输入是奇数,则定为2 3 ? ? * 若是偶数,则定为2 2 ? ? * 剩余一个偶数再分成两个素数,问题迎刃而解 * PS:显然n<8无解 */ #include <iostream> #include < ...
/* * [题意] * 判断n!是否能被m整除(n!/m = 整数) * * [解题方法] * 对m分解素因子,得出每个素因子的个数 * 若某个素因子个数大于n!中此因子的个数,则不可整除 */ #include <iostream> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <math.h> using namespace std; #define LL long long #define ...
        新手请进:扩展欧几里德入门 /* * 直接Egcd就得出|x|+|y|最小的解 * 不知道为什么可以这样,我觉得分4种情况讨论的做法更靠谱些 */ #include <iostream> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <math.h> using namespace std; #define LL long long #define M 105 #define inf 0x3ff ...
Global site tag (gtag.js) - Google Analytics