Search found 215 matches

by ImLazy
Wed Nov 14, 2007 7:52 am
Forum: Algorithms
Topic: Suffix tree construction
Replies: 13
Views: 4580

maxdiver wrote:you could find this book in the Internet in a free electronic version.
Could you give me a link?
by ImLazy
Wed Nov 14, 2007 7:20 am
Forum: Algorithms
Topic: K'th Shortest Path
Replies: 6
Views: 3438

The offical report of Yokohama 2006 gives the algorithm.
by ImLazy
Fri Oct 12, 2007 10:58 am
Forum: Algorithms
Topic: K'th Shortest Path
Replies: 6
Views: 3438

I heard that the generalizations of Dijkstra can not handle loopless paths.
by ImLazy
Mon Oct 08, 2007 2:12 pm
Forum: C++
Topic: Compile error on priority_queue.
Replies: 6
Views: 3653

It looks like the compiler thinks that "priority_queue<int, vector<int>, MyLess> que(MyLess(a));" is a function prototype, instead of a variable. Maybe just as you said, we can see the compiler outputs " which is of non-class type ". So I change the line to: priority_queue<int, vector<int>, MyLess>...
by ImLazy
Mon Oct 08, 2007 10:49 am
Forum: C++
Topic: Compile error on priority_queue.
Replies: 6
Views: 3653

:-? You can try, I change the line

Code: Select all

priority_queue<int> que( MyLess(a) ); 
to

Code: Select all

priority_queue<int, vector<int>, MyLess> que( MyLess(a) );
still the same compilation error.
by ImLazy
Mon Oct 08, 2007 4:53 am
Forum: C++
Topic: Compile error on priority_queue.
Replies: 6
Views: 3653

Compile error on priority_queue.

#include <queue> using namespace std; struct MyLess: public less<int> { const int* a; MyLess(const int* _a) { a = _a; } bool operator () (int i, int j) const { return a[i] > a[j]; } }; int main() { int a[100]; priority_queue<int> que( MyLess(a) ); que.push(1); return 0; } But I get this compilation...
by ImLazy
Sat Oct 06, 2007 4:25 am
Forum: Algorithms
Topic: Number of different necklets.
Replies: 16
Views: 4757

Oh, I see.
The result r = (ans / N) % 2003, so ans = N(2003x + r) = 2003Nx + Nr, so ans % 2003N = Nr, so r = (ans % 2003N) / N.
Thank you again. :D
by ImLazy
Fri Oct 05, 2007 2:35 pm
Forum: Algorithms
Topic: Number of different necklets.
Replies: 16
Views: 4757

Yes, I see. Thank you very much, MF. You are so erudite. You see, I'm not smart, and get understand very slowly. Thank you for your patience. By the way, I find your modexp() function doesn't work very well when N > 46340. The " b = (b * b) % MOD " may overflow 2^31 when b > 46340. I just add a " b ...
by ImLazy
Thu Oct 04, 2007 5:27 pm
Forum: Algorithms
Topic: Number of different necklets.
Replies: 16
Views: 4757

So what's Euler's theorem? From your code I think it is:

Code: Select all

(a / N) % m == (a * N ^ m - 2) % m. Only for gcd(N, m) == 1
Am I right?
I just see in your output, when N is multiple of 2003, the answer is always 0.
by ImLazy
Thu Oct 04, 2007 7:17 am
Forum: Algorithms
Topic: Number of different necklets.
Replies: 16
Views: 4757

Sorry, I don't quite understand the Just find modular inverse of N, and multiply by it . In my algorithm, if I want to get the solution for N = 99999 and N = 99998, I need to do 2 times of DP, one O(7*7*7*99999) and one O(7*7*7*99998). That makes my program slow. I think your algorithm can get all t...
by ImLazy
Thu Oct 04, 2007 6:25 am
Forum: Algorithms
Topic: Number of different necklets.
Replies: 16
Views: 4757

The answer is right, but the speed is a little bit slow. In fact, the requirement of the problem is to output the answer mod 2003, not mod 10000. If without the last dividing by N , just mod 2003, I can mod dp[n][j][k] by 2003 at every step of the DP. But now with the dividing by N at last, it is a ...
by ImLazy
Tue Oct 02, 2007 10:00 am
Forum: Algorithms
Topic: Number of different necklets.
Replies: 16
Views: 4757

OK, now the output seems to be right. Thank you. :D

Could you give some link to the Burnside's lemma? I search it on Math World and get this page. I don't quite understand what it says.
by ImLazy
Tue Oct 02, 2007 9:30 am
Forum: Algorithms
Topic: Number of different necklets.
Replies: 16
Views: 4757

What's the result of gcd(N, 0)? I just define it 0.
And your output for input 1, 2, 3, 4, 5, 6 are 0, 0, 0, 10, 0, 49. Are you sure this algorithm is right?
by ImLazy
Tue Oct 02, 2007 8:17 am
Forum: Algorithms
Topic: Number of different necklets.
Replies: 16
Views: 4757

Sorry, I don't quite understand. Could you show me a sample?
For example, could you show me the process how to get the answer when N = 5?
by ImLazy
Tue Oct 02, 2007 5:23 am
Forum: Algorithms
Topic: Number of different necklets.
Replies: 16
Views: 4757

Number of different necklets.

Given pearls of 7 different colors, to make a necklet. Any two adjacent pearls mustn't have same colors. The first and the last pearls are also adjacent. Given the length of the necklet N (N < 100000). Please calculate the number of different ways to make the necklet. The answer may be very big, jus...

Go to advanced search