fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class CandyDrawing {
  5. 	typedef unsigned long long ull;
  6.  
  7. 	unsigned long long pw(ull a, int e, ull mod) {
  8. 		if(e <= 0) return 1;
  9. 		ull x =pw(a,e/2,mod);
  10. 		x =(x*x)%mod;
  11. 		if(e%2 != 0) x =(x*a)%mod;
  12. 		return x;}
  13.  
  14. 	public: int findProbability(int N, int K, int MOD) {
  15. 		ull mod =MOD;
  16. 		ull modSq =mod*mod;		
  17. 		vector< vector<ull> > A(32,vector<ull>(K+1,mod));
  18. 		vector< vector<ull> > A2 =A;
  19. 		for(int i =0; i <= 30; i++) for(int j =0; j <= K; j++) if((N>>i) < j || (N>>i) == 0) A[i][j] =0;
  20. 		for(int i =0; i <= 30; i++) A[i][0] =1;
  21. 		for(int i =0; i <= 30; i++) for(int j =0; j <= K; j++) if((N>>(i+1)) < j || (N>>i) == 0) A2[i][j] =0;
  22. 		for(int i =0; i <= 30; i++) A2[i][0] =1;
  23.  
  24. 		vector<ull> inv(K+9,1);
  25. 		for(int i =1; i <= K; i++) inv[i] =pw(i,MOD-2,mod);
  26. 		vector< vector<ull> > powNs(32,vector<ull>(K+1,1));
  27. 		for(int i =0; i <= 30; i++) for(int j =1; j <= K; j++) {
  28. 			powNs[i][j] =(powNs[i][j-1]*((N>>i)+1))%mod;
  29. 			powNs[i][j] =(powNs[i][j]*inv[j])%mod;}
  30.  
  31. 		for(int s =29; s >= 0; s--) for(int j =0; j <= K; j++) {
  32.  
  33. 			if(A2[s][j] == mod) {
  34. 				ull decP =1;
  35. 				for(int i =0; i <= j; i++) {
  36. 					ull c =(decP*powNs[s][i])%mod;
  37. 					decP =(decP*((N>>(s+1))-j+i+1))%mod;
  38. 					if(i&1 && A2[s][j] >= 2*modSq) A2[s][j] -=2*modSq;
  39. 					if((j-i)&1) A2[s][j] +=modSq-c*A[s+1][j-i];
  40. 					else A2[s][j] +=c*A[s+1][j-i];}
  41. 				A2[s][j] %=mod;}
  42.  
  43. 			if(A[s][j] == mod) {
  44. 				if((N>>s)&1) {
  45. 					for(int i =0; i < j; i++) {
  46. 						if(i&1 && A[s][j] >= 2*modSq) A[s][j] -=2*modSq;
  47. 						A[s][j] +=A[s+1][i]*A2[s][j-i-1];}
  48. 					A[s][j] %=mod;
  49. 					A[s][j] =(A[s][j]*((N>>(s+1))+1))%mod;}
  50. 				for(int i =0; i <= j; i++) {
  51. 					if(i&1 && A[s][j] >= 2*modSq) A[s][j] -=2*modSq;
  52. 					A[s][j] +=A[s+1][i]*A2[s][j-i];}
  53. 				A[s][j] %=mod;}
  54. 			}
  55.  
  56. 		return A[0][K];}
  57. 	};
Compilation error #stdin compilation error #stdout 1.09s 3488KB
comments (?)
stdin
copy 
1000000000
1000
1000000009
compilation info 
/usr/lib/gcc/i486-linux-gnu/4.8/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/wilEgP
TC SRM 629 div1 950pt
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!