\(N \ \&\ i \ = \ i\) Bo'lishi uchun \(i\)ning ikkilikdagi birlari \(N\) ning ikkilikka o'tkazganimizdagi birlari soni bilan ustma-ust tushishi kerak
bundan \(N\) ning 2 likdagi ko'rinishida 1 turgan bo'lsa u birni shundayligicha qoldiramiz yoki \(0\) bilan alishtiramiz, shunda bizda mavjud kombinatsiyalar soni \(2 ^ {birlar\_soni(n)}\) ga teng bo'lib qoladi. \(i = 0\) holat sanalmagani uchun umumiy javob \(2 ^ {birlar\_soni(n)}-1\) bo'ladi.
Python yechim:
print(2**(bin(int(input())).count('1')) - 1)C++ Yechim:
#include <iostream>
using namespace std;
int main(){
long long n;
cin >> n;
cout << (1LL<<__builtin_popcountll(n)) - 1;
return 0;
}
ASCII bo'yicha kichik lotin harflarining ichida eng kichigi ‘a’ hisoblanadi.
Faqat kichik lotin harflaridan foydalanganimiz uchun kiritilgan satr oxiriga ‘a’ harfini qo'shish yetarli.
!!! Leksikografik tartib.
s satr t satrdan kichik deb qachon aytiladi?
Biz avvalo \(s[i] != t[i]\) shartni qanoatlantiruvchi eng kichik indeksni topamiz. (Agar \(s[i] < t[i]\) bo'lsa s satr kichkina aks holda t satr kichkina hisoblanadi)
Agar bunday indeks mavjud bo'lmasa satrlardan uzunligi kichigi kichik hisoblanadi. Agar uzunliklar ham teng bo'lsa ushbu satrlar teng hisoblanadi.
Python yechim:
print(input() + 'a')C++ yechim:
#include <iostream>
using namespace std;
int main(){
string s; cin >> s;
cout << s + "a";
return 0;
}
Bizda \(C_n^k\% \ 2 \ = \ 1\) bo'lishi uchun Lucas teoremassiga ko'ra \(n\ \& \ k \ =\ k\) shart bajarilishi kerak va bizda \(C_n^k\% \ 2 \ = \ 1\) bo'lsa \(C_n^{n-k}\% \ 2 \ = \ 1\) ham to'g'ri bo'ladi, chunki \(C_n^k\ =\ C_n^{n - k}\). Bunda har bir juftlikning yig'indisi \(n\) ga teng bo'ladi. Demak, biz nechta juftlik borligini topib \(n\) ga ko'paytirib qo'yishimiz yetarli.
Python yechim:
n = int(input())
x = (1 << bin(n).count('1'))
print((x // 2) * n)C++ Yechim:
#include <iostream>
using namespace std;
int main(){
long long n;
cin >> n;
cout << (1LL<<__builtin_popcountll(n)) / 2 * n;
return 0;
}
Bu va bunga o'xshash masalaning mashxur yechimi \(dp\) yechim bo'lib u quyidagicha:
\(dp[i] = \sum _{j = max(i - k,0)}^{i-1} dp[j]\).
Bu masalada \(N\)ning chegarasi juda katta shu sababli biz buni \(dp\) bilan ishlay olmaymiz, shuning uchun bizda \(N \le K\) bo'lsa \(dp\)
qilib yechisimiz mumkin, aks holda biz bu masalani Matrix exponentiation bilan ishlaymiz, ya'ni dastlab K x K matritsa yasab olamiz, va uni \(N - K\) - darajasini topamiz, so'ngra uni \(dp\) bilan yasalga 1 ga K matritsamizga ko'paytirib olamiz va javob olamiz.
Python yechim:
n, k = map(int, input().split())
mod = 10**9 + 7
dp = [0 for _ in range(k)]
dp[0] = 1
if k > 1:
dp[1] = 1
for i in range(2, k):
dp[i] = (dp[i-1]<<1) % mod
e = [[0 for i in range(k)] for _ in range(k)]
a = [[0 for i in range(k)] for _ in range(k)]
for i in range(k):e[i][i] = 1
for i in range(k-1):
a[i+1][i] = 1
for i in range(k):
a[i][k-1] = 1
def F(a, b):
global k
res = [[0 for i in range(k)] for _ in range(k)]
for q in range(k):
for u in range(k):
s = 0
for i in range(k):
s = (s + a[q][i] * b[i][u]) % mod
res[q][u] = s
return res
def binpow(a, d):
global e
if d == 0:
return e
if d == 1:
return a
if d % 2 == 0:
res = binpow(a, d // 2)
return F(res, res)
return F(a, binpow(a, d - 1))
b = binpow(a, n - k)
res = 0
for i in range(k):
res = (res + dp[i] * b[i][k-1]) % mod
print(res % mod)C++ Yechim:
#include <iostream>
#include <vector>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int n, k;
vector <vector <int>> a, e;
vector <vector <int>> operator *(vector <vector <int>> x, vector <vector <int>> y){
vector <vector <int>> res(k, vector <int>(k, 0));
for (int q = 0; q < k; ++ q)
for (int u = 0; u < k; ++ u){
int s = 0;
for (int i = 0; i < k; ++ i)
s = (s + x[q][i] * y[i][u]) % mod;
res[q][u] = s;
}
return res;
}
vector <vector <int>> binpow(vector <vector <int>> v, int d){
if (d == 0) return e;
if (d == 1) return v;
if ((d&1) == 0){
auto res = binpow(v, d>>1LL);
return res * res;
}
return v * binpow(v, d - 1);
}
void solve(){
cin >> n >> k;
vector <int> dp(k);
dp[0] = 1;
if (k > 1) dp[1] = 1;
for (int i = 2; i < k; ++ i) dp[i] = (dp[i-1] << 1LL) % mod;
a.assign(k, vector <int>(k, 0));
e.assign(k, vector <int>(k, 0));
for (int i = 0; i < k; ++ i) e[i][i] = 1, a[i][k-1] = 1;
for (int i = 0; i + 1 < k; ++ i) a[i+1][i] = 1;
auto b = binpow(a, n - k);
int res = 0;
for (int i = 0; i < k; ++ i)
res = (res + dp[i] * b[i][k-1]) % mod;
cout << res;
}
signed main(){
cin.tie(nullptr)->ios::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t --)
solve();
return 0;
}
Bu masalani yechish uchun aniq bir algorithm yo'q va bizga kerak bo'ladigan masalaning yagona g'oyasi har bir i - chi index uchun undan o'ng tomonda turuvchi va unga eng yaqin bo'lgan raqamlarning indexini saqlab olish. Keyin bizga L,R,K sonlari kiritilganda \(R - a[L - 1][9]\) bu son \(K\) dan katta yoki teng bo'lsa, bizda birinchi chiqadigan son \(9\) bo'ladi, keyin \(L\) ni \(a[L - 1][9]\) ga o'zgartirib qo'yamiz hamda \(K\) ni bittaga kamaytiramiz, shu tarzda \(K\) nol bo'lib qolguncha davom etamiz. Agar bizda \(R - a[L - 1][9]\) bu son \(K\) dan kichik bo'lsa \(9\) ni o'rniga \(8\) yozamiz va shu tariqa raqamlarni kichiklashtirib boramiz.
Python yechim:
n,q = map(int,input().split())
s = input()
a = [[0 for __ in range(10)] for ___ in range(n + 1)]
b = [10**6 for __ in range(10)]
for i in range(n - 1,-1,-1):
a[i+1] = b.copy()
b[int(s[i])] = i + 1
a[0] = b.copy()
al = []
ar = []
ak = []
for i in range(q):
l,r,k = map(int,input().split())
l -= 1
k = min(k,r - l)
cnt = 0
while k > 0:
R = 9
while r - a[l][R] + 1 < k:
R -= 1
if not (cnt == 0 and R == 0):
print(R,end = '')
cnt += 1
k -= 1
l = a[l][R]
if cnt == 0:
print(0,end = '')
print()
C++ Yechim:
#include <iostream>
#include <vector>
using namespace std;
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,q;
string s;
cin >> n >> q >> s;
vector<vector<int>>a (n + 1,vector<int>(10));
vector<int> b(10,1e6);
for(int i = n - 1;i >= 0; -- i){
a[i + 1] = b;
b[s[i] - '0'] = i + 1;
}
a[0] = b;
int R;
while(q --){
int l,r,k;
cin >> l >> r >> k;
-- l;
k = min(k,r - l);
int cnt = 0;
while(k > 0){
R = 9;
while(r - a[l][R] + 1 < k){
R --;
}
if(cnt == 0 && R == 0);
else {
cout << R;
++ cnt;
}
-- k;
l = a[l][R];
}
if(cnt == 0) cout << 0;
cout << '\n';
}
return 0;
}
Telegram kanalimizga obuna bo'ling