fork download
copy 
  1. // coding in the memory of Legend :) 
  2.  
  3.  
  4. //~ mail ID : neernpatel@gmail.com
  5. //~ Author : DrexDelta
  6. //~ codechef : drexdelta , hackerRank : drexdelta , codeforces : drexdelta1
  7. //~ Contact Info : neernpatel@gmail.com
  8.  
  9.  
  10. #include<iostream>
  11. #include <cctype>
  12. #include <cerrno>
  13. #include <cfloat>
  14. #include <ciso646>
  15. #include <climits>
  16. #include <clocale>
  17. #include <cmath>
  18. #include <csetjmp>
  19. #include <csignal>
  20. #include <cstdarg>
  21. #include <cstddef>
  22. #include <cstdio>
  23. #include <cstdlib>
  24. #include <cstring>
  25. #include <ctime>
  26. #include <ccomplex>
  27. #include <cfenv>
  28. #include <cinttypes>
  29. #include <cstdbool>
  30. #include <cstdint>
  31. #include <ctgmath>
  32. #include <cwchar>
  33. #include <cwctype>
  34. #include <algorithm>
  35. #include <bitset>
  36. #include <complex>
  37. #include <deque>
  38. #include <exception>
  39. #include <fstream>
  40. #include <functional>
  41. #include <iomanip>
  42. #include <ios>
  43. #include <iosfwd>
  44. #include <iostream>
  45. #include <istream>
  46. #include <iterator>
  47. #include <limits>
  48. #include <list>
  49. #include <locale>
  50. #include <map>
  51. #include <memory>
  52. #include <new>
  53. #include <numeric>
  54. #include <ostream>
  55. #include <queue>
  56. #include <set>
  57. #include <sstream>
  58. #include <stack>
  59. #include <stdexcept>
  60. #include <streambuf>
  61. #include <string>
  62. #include <typeinfo>
  63. #include <utility>
  64. #include <valarray>
  65. #include <vector>
  66. #include <array>
  67. #include <unordered_map>
  68. #include <unordered_set>
  69.  
  70.  
  71. using namespace std;
  72.  
  73. #define F first
  74. #define S second
  75. #define MP make_pair
  76. #define PB push_back
  77. #define UB upper_bound
  78. #define LB lower_bound
  79. #define ER erase
  80. #define EN end()
  81. #define B begin()
  82. #define I insert
  83. #define OPTIMIZE ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  84. #define int ll
  85. #define endl "\n"
  86. #define CO cout <<
  87. #define CI cin >>
  88. #define NL cout << endl;
  89. #define DBG {int debug ; cin >> debug;}
  90. #define AND &&
  91. #define OR ||
  92. #define XOR ^
  93. #define OFLUSH fflush(stdout);
  94. #define IFLUSH fflush(stdin);
  95. #define LEN(x) ((int)x.length())
  96.  
  97. #define rep(i,x) for(int i = 0 ; i < x ; i++)
  98. #define rep1(i,x) for(int i = 1 ; i <= x ; i++)
  99.  
  100. #define repl(var,start_val,limit_val) for(int var = start_val ; var <= limit_val ; var++)
  101. #define perl(var,start_val,limit_val) for(int var = start_val ; var >= limit_val ; var--)
  102.  
  103. #define y1 qwert
  104. #define y2 trewq
  105. #define x1 asdfg
  106. #define x2 gfdsa
  107.  
  108. typedef long long ll;
  109. typedef pair<int,int> ii;
  110. typedef vector<int> vi;
  111. typedef set<int> si;
  112. typedef multiset<int> msi;
  113. typedef long double ld;
  114.  
  115. const ll maxn = 2e6+6 ;
  116. const ll MOD = 1e9 + 7;
  117.  
  118. bool comparator(int i , int j)
  119. {
  120.     return (i < j);
  121. }
  122.  
  123. ll power(ll x, ll i)
  124. {
  125. 	ll ans = 1;
  126. 	while(i > 0)
  127. 	{
  128. 		if(i&1)
  129. 			ans = (ans*x)%MOD;
  130. 		i >>=1;
  131. 		x = (x*x)%MOD;
  132. 	}
  133. 	return ans;
  134. }
  135.  
  136. ll power(ll x, ll i,ll mod)
  137. {
  138. 	ll ans = 1;
  139. 	while(i > 0)
  140. 	{
  141. 		if(i&1)
  142. 			ans = (ans*x)%mod;
  143. 		i >>=1;
  144. 		x = (x*x)%mod;
  145. 	}
  146. 	return ans;
  147. }
  148.  
  149. ll modInverse(ll x, ll mod)
  150. {
  151. 	return power(x , mod-2,mod);
  152. }
  153.  
  154. bool isPalindrome(string s)
  155. {
  156. 	int limit = s.length()/2;
  157. 	for(int i =  0 ; i < limit ; i++)
  158. 	{
  159. 		if(s[i] != s[s.length()-i-1])
  160. 			return 0;
  161. 	}
  162. 	return true;
  163. }
  164.  
  165. ll gcd(ll x, ll y)
  166. {
  167. 	ll t;
  168. 	while(y != 0)
  169. 	{
  170. 		t = x%y;
  171. 		x = y;
  172. 		y = t;
  173. 	}
  174. 	return x;
  175. }
  176.  
  177. bool isVowel(char ch){
  178.  
  179.     if(ch == 'a' || ch == 'i' || ch == 'e' || ch == 'u' || ch == 'o' || ch == 'y'){
  180.         return true;
  181.     }
  182.     return false;
  183. }
  184.  
  185. bool isPrime(int n)
  186. {
  187. 	int root = sqrt(n);
  188. 	for(int i = 2 ; i <= root ; i++) if(n%i == 0) return 0;
  189. 	return 1;
  190. }
  191.  
  192. // Geometry
  193. ///////////////
  194.  
  195. ld getDis(ld x1 ,ld y1,ld x2,ld y2){
  196. 	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
  197. }
  198.  
  199. ld getDisSquare(ld x1,ld y1,ld x2,ld y2){
  200. 	return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
  201. }
  202.  
  203. /////////////
  204. bool isSquareHelper(int x1 , int y1 , int x2 , int y2 , int x3 , int y3 , int x4 , int y4){
  205.  
  206. 	ld d1,d2,d3,d4,d5,d6;
  207. 	d1 = getDisSquare(x1,y1,x2,y2);
  208. 	d2 = getDisSquare(x2,y2,x3,y3);
  209. 	d3 = getDisSquare(x3,y3,x4,y4);
  210. 	d4 = getDisSquare(x4,y4,x1,y1);
  211.  
  212. 	if(d1 == d2 && d1 == d3 && d1 == d4){
  213.  
  214.  
  215. 		d5 = getDisSquare(x1,y1,x3,y3);
  216. 		d6 = getDisSquare(x2,y2,x4,y4);
  217. 		if(d5 == d6){
  218. 			return 1;
  219. 		}
  220.  
  221. 	}
  222. 	return 0;
  223.  
  224. }
  225.  
  226. // pass 4 points in any order, 
  227. // returns 1 if it forms square, else returns zero
  228.  
  229. bool isSquare(int x1 ,int y1 , int x2 , int y2 , int x3 , int y3 ,int x4 , int y4){
  230.  
  231.     if(	isSquareHelper(x1,y1,x2,y2,x3,y3,x4,y4) || 
  232.     	isSquareHelper(x1,y1,x2,y2,x4,y4,x3,y3) || 
  233.     	isSquareHelper(x1,y1,x3,y3,x2,y2,x4,y4)	)
  234.     	return 1;
  235.     else
  236.     	return 0;
  237.  
  238. }
  239.  
  240. ////////
  241. bool isEqualateralTriangle(int x1, int y1,int x2, int y2, int x3, int y3){
  242.  
  243. 	int d1 = getDisSquare(x1,y1,x2,y2);
  244. 	int d2 = getDisSquare(x2,y2,x3,y3);
  245. 	int d3 = getDisSquare(x3,y3,x1,y1);
  246. 	if(d1 == d2 && d1 == d3){
  247. 		return 1;
  248. 	}
  249. 	else
  250. 		return 0;
  251.  
  252. }
  253.  
  254. // checking if , first piont is right angle
  255. bool isRightAngleTriangleHelper(int x1, int y1 ,int x2 , int y2 , int x3 , int y3){
  256.  
  257. 	int d1 = getDisSquare(x1,y1,x2,y2);
  258. 	int d2 = getDisSquare(x2,y2,x3,y3);
  259. 	int d3 = getDisSquare(x3,y3,x1,y1);
  260.  
  261. 	if(d2 == (d1 + d3)){
  262. 		return 1;
  263. 	}
  264. 	return 0;
  265.  
  266. }
  267.  
  268. bool isRightAngleTriangle(int x1, int y1, int x2 ,int y2 ,int x3 , int y3){
  269.  
  270. 	if(isRightAngleTriangleHelper(x1,y1,x2,y2,x3,y3) || 
  271. 		isRightAngleTriangleHelper(x2,y2,x3,y3,x1,y1) ||
  272. 		  isRightAngleTriangleHelper(x3,y3,x1,y1,x2,y2)) 
  273. 		return 1;
  274.  
  275. 	return 0;
  276.  
  277. }
  278.  
  279. bool areCollinear(int x1, int y1,int x2 , int y2 , int x3 , int y3){
  280.  
  281. }
  282.  
  283. // eratoshenes sieve ...
  284. // Once eratoshtenes is activated, use the isPrime function below it,
  285. // and deactivate above function
  286.  
  287. /*
  288.  
  289. int lp[maxn];
  290. vector<int> pr;
  291. void generatePrimes()
  292. {
  293. 	for (int i=2; i<=maxn; ++i)
  294. 	{
  295. 		if (lp[i] == 0)
  296. 		{
  297. 			lp[i] = i;
  298. 			pr.push_back (i);
  299. 		}
  300. 		for (unsigned j=0; j<pr.size() && pr[j]<=lp[i] && i*pr[j]<=maxn;)
  301. 		{
  302. 			lp[i * pr[j]] = pr[j];
  303. 			j++;
  304. 		}
  305. 	}
  306. 	return;
  307. }
  308.  
  309. bool isPrime(int n)
  310. {
  311. 	int root = sqrt(n);
  312. 	for(int i = 0 ; i < pr.size() && pr[i] <= root ; i++) if(n%pr[i] == 0) return 0;
  313. 	return 1;
  314. }
  315.  
  316. */
  317.  
  318. /////////////////////////
  319. // declaration section //
  320. /////////////////////////
  321.  
  322. int ncr[1100][1100];
  323. int k ;
  324. string s;
  325.  
  326. void getInput(){
  327.  
  328. 	cin >> s;
  329. 	cin >>k;
  330. }
  331.  
  332. void getAnswer(){
  333.  
  334. }
  335.  
  336. vi s1 , s2 , *dp1 , *dp2;
  337.  
  338. int getCount(int index , int remOnes){
  339.  
  340. 	// cout << " index " << index << " rem ones " << remOnes << endl;
  341. 	if(remOnes == 0)return 1;
  342.  
  343. 	if(index == LEN(s)){
  344. 		return 0;
  345. 	}
  346.  
  347. 	int ret = 0;
  348.  
  349. 	if(s[index] == '1'){
  350.  
  351. 		int remLen = LEN(s)-index-1;
  352. 		ret = ncr[remLen][remOnes];
  353. 		// cout << " before next call of index " << index << " rem ones " << remOnes  << " ret " << ret << endl;
  354. 		ret += getCount(index+1,remOnes-1);
  355. 		// cout << " leaving index " << index << " rem ones " << remOnes << endl;
  356.  
  357. 	}
  358. 	else{
  359. 		ret = getCount(index+1,remOnes);
  360. 	}
  361.  
  362. 	return ret;
  363.  
  364. }
  365.  
  366. bool check(int ones){
  367.  
  368. 	//cout << " ones " << ones << endl;
  369. 	//if(ones==0)return false;
  370.  
  371. 	int counts , reps = 1;
  372.  
  373. 	while(ones != 1){
  374.  
  375. 		counts = 0;
  376. 		while(ones != 0){
  377. 			if(ones&1)counts++;
  378. 			ones>>=1;
  379. 		}
  380. 		ones = counts;
  381. 		reps++;
  382.  
  383. 	}
  384. 	//cout << " reps " << reps << " k " << k << endl;
  385.  
  386. 	return(reps >= k);
  387.  
  388. }
  389. void solve(){
  390.  
  391. 	int ans = 0;
  392.  
  393. 	if(k==0){
  394. 		cout << 1 << endl;
  395. 		return;
  396. 	}
  397.  
  398. 	dp1 = &s1 , dp2 = &s2;
  399.  
  400. 	if(k==1){
  401. 		cout << LEN(s)-1 << endl;
  402. 		return;
  403. 	}
  404.  
  405. 	repl(i,1,1010){
  406.  
  407. 		if(check(i) && i <= LEN(s)){
  408.  
  409. 			//cout << " check sucessful for " << i << endl;
  410. 			int x =  getCount(0,i);
  411. 			//cout << " adding " << x << endl;
  412. 			ans = (ans + x)%MOD;
  413. 			//cout << " ans " << ans << endl;
  414. 			//NL NL NL
  415.  
  416. 		}
  417.  
  418. 	}
  419. 	//cout << getCount(0,2) << endl;
  420.  
  421. 	cout << ans << endl;
  422.  
  423. }
  424.  
  425. void pre(){
  426.  
  427. 	//cout << " pre called " << endl;
  428. 	rep(i,1050){
  429. 		ncr[i][0] = 1;
  430. 	}
  431.  
  432. 	repl(i,1,1049){
  433. 		repl(j,1,i){
  434. 			ncr[i][j] = (ncr[i-1][j] + ncr[i-1][j-1])%MOD;
  435. 		}
  436. 	}
  437.  
  438. 	// rep(i,10){
  439. 	// 	rep(j,i+1){
  440. 	// 		cout << ncr[i][j] << " " ;
  441. 	// 	}
  442. 	// 	NL
  443. 	// }
  444.  
  445. }
  446.  
  447. signed main(){
  448.  
  449.     OPTIMIZE
  450.     //check(2) ;
  451.     pre();
  452.  
  453.     getInput();
  454.     solve();
  455.     return 0;
  456.  
  457. }
  458.  
Success #stdin #stdout 0s 24696KB
comments (?)
stdin
copy 
111111011
2
stdout
copy 
498
https://ideone.com/OLVWxL
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!