OJ Board

maxdiver wrote:you could find this book in the Internet in a free electronic version.

Could you give me a link?

The offical report of Yokohama 2006 gives the algorithm.

I heard that the generalizations of Dijkstra can not handle loopless paths.

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>...

You can try, I change the line to still the same compilation error.

#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...

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.

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 ...

So what's Euler's theorem? From your code I think it is: Am I right?
I just see in your output, when N is multiple of 2003, the answer is always 0.

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...

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 ...

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

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.

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?

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?

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...