#include <iostream> #include "message.h" #include "futbol.h" using namespace std; long long LucasUtil(long long n, long long k, long long p) { long long* triangle = new long long[k+1]; long long i, j; for(i = 1; i <= k; i++) { triangle[i] = 0; } triangle[0] = 1; for(i = 1; i <= n; i++) { for (j = min(i, k); j > 0; j--) { triangle[j] = (triangle[j] + triangle[j-1])%p; } } delete [] triangle; i = triangle[k]; return i; } long long Lucas(long long n, long long k, long p) { if(k == 0) { return 1; } long long ni = n%p, ki = k%p; return (Lucas(n/p, k/p, p) * LucasUtil(ni, ki, p)) % p; } int main() { if(MyNodeId() == 0) { long long n = GetN(), k = GetK(), p = GetP(), i, w = 0; for(i = 0; i <= k; i++) { w += Lucas(n, i, p); w %= p; } cout << w << "\n"; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <iostream> #include "message.h" #include "futbol.h" using namespace std; long long LucasUtil(long long n, long long k, long long p) { long long* triangle = new long long[k+1]; long long i, j; for(i = 1; i <= k; i++) { triangle[i] = 0; } triangle[0] = 1; for(i = 1; i <= n; i++) { for (j = min(i, k); j > 0; j--) { triangle[j] = (triangle[j] + triangle[j-1])%p; } } delete [] triangle; i = triangle[k]; return i; } long long Lucas(long long n, long long k, long p) { if(k == 0) { return 1; } long long ni = n%p, ki = k%p; return (Lucas(n/p, k/p, p) * LucasUtil(ni, ki, p)) % p; } int main() { if(MyNodeId() == 0) { long long n = GetN(), k = GetK(), p = GetP(), i, w = 0; for(i = 0; i <= k; i++) { w += Lucas(n, i, p); w %= p; } cout << w << "\n"; } return 0; } |