2009/02/06 22:14 思路很简单就是暴力,只要注意下中间过程取mod的时候
1.对a分解素数,得到pi,ci分别表示第i个素因子和它的个数
2.ci*b,就是a^b=p1^(c1*b) * .... * pi^(ci*b)
3.所求的就是ans=(1+p1+p1^2+...+p1^(c1*b))*()...*(1+pi+pi^2+...+pi^(ci*b))
4.由于b 比较大，所以求1+p1+p1^2+...+p1^(c1*b)的时候使用二分,要注意取mod,小心溢出
#include <iostream>
using namespace std;
typedef unsigned long long llong;
int p[4000],len=0,top[32][2],tlen;
bool s[7072]={true,true};
void split |
2009/02/06 18:37 以下是baidu找的题解
以单词为点，能前后相连的单词之间连边，得到一个有向图，求长度为奇数且小于等于N的不同的S->T的路径数。设邻接矩阵为A，则可通过求A
+ A ^ 3 + ... + A ^ N求解。构造一个矩阵后可通过logN次矩阵乘求解。
以下是本人代码
/*
求和的时候稍微做了点优化
*/
#include <iostream>
#include <string>
using namespace std;
#define MAX_SIZE 30
char w[MAX_SIZE][11],ttmp[11];
int moudle,k,size;
inline int fid(char* k){int i |
2009/02/06 17:48 经典的用矩阵解决的题目.
f(k)表示数列的第k项,那么可以很容易的得到
f(n) 1 1 f(1)
= 的n-1次方 *
|
2009/02/06 17:45 一开始土土dfs,不是WA就是TLE .....最后发现原来可以回头走的-_______________-那确实没做过够麻烦想了好久......
最后竟然发现开始点居然被我标记了....取消标记后一次AC的说...
dp[100][100][16]中dp[x][y][t]用来保存(x,y)点在剩余时间还为t时到达终点的方案数.
然后就是土土的dfs....-__________-学习到不少的说,还学到一个小的剪枝
就是如果(x,y)和终点的曼哈顿距离(abs(x1-x2)+abs(y1-y2))大于t,那么肯定就不行拉.
效果还是比较明显的说-_-
下面是代码也..
#in |
2009/02/06 17:44 按照右端点从小到大的排
然后贪心
其实这也是在大牛的指导下完成的............
#include <iostream>
#include <algorithm>
using namespace std;
struct XML
{
int _strat_vale,_end_vlaue;
bool operator<(const |
2009/02/06 17:40 题目的意思很明白,就是可以同时改变最多5个的颜色(既,自身,上,下,左,右)一开始赤裸裸的BFS,很显然是MLE..
这里不讨论暴力解的情况了....-______________________-暴力是好东西可是偶不会,苍天也.......用暴力的大牛们勿鄙
考虑到状态的特殊性,一个节点要么白色要么黑色,很容易想到用2进制表示,16个节点,最多用16个表示就OK了.
选取的时候自然是去int(32位),因为需要移位
第一次写也不知道这是不是传说中的hash... |
2009/02/06 17:35 1.先生成小数据.(用暴力)
下面是1~32的数据：
1:0
2:1
3:10
4:11
5:100
6:101
7:110
8:111
9:1000
10:1001
11:1010
12:1011
13:1100
14:1101
15:1110
16:10000
17:10001
18:10010
19:10011
20:10100
21:10101
22:10110
23:11000
24:11001
25:11010
26:11100
27:100000
28:100001
29:100010
30:100011
31:100100
32:100101
通过位数分类,f[i]表示i位所 |
2009/02/06 17:34 生成几组小数据，马上得到规律，a+b满足
f[1]=2;
f[2]=3;
f[3]=5;
....
f[n]=f[n-1]+f[n-2](n>=3)
由于题目需要对2^64取mod
所以直接使用矩阵乘法就可以快速的解决
f[n] 1 1 f[n-1]
= *
f[n-1] 1 0 f[n-2]
一直化下去可以得到实际上:
f[n] |
2009/02/06 17:30 类似PKU上面的一个题目:
一开始以为是用母函数，可是数据ms不小的说，于是从三进制入手
1.先从最简单的例子开始说起:
|
2009/02/06 17:27 Calculate a + b
Input
The input will consist of a series of pairs of integers a and b,separated by a space, one pair of integers per line.
Output
For each pair of input integers a and b you should output the sum of a and b in one line,and with one line of output for each line in input.
Sample Input
1 5
2 3
Sample Output
6
5
|
| | |
