基德KID.1412
- 浏览: 316776 次
- 性别:
- 来自: 珠海
-
最新评论
-
xialluyouyue：
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294：
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412：
su1216 写道竖线代表或者，不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216：
竖线代表或者，不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu：
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
文章列表
莫比乌斯函数完整定义的通俗表达：
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 ...