算法进阶-递归算法

High11 大水题

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
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b) { return (a + b) % MOD; }
inline ll submod(ll a, ll b) { return (a - b + MOD) % MOD; }
inline ll mulmod(ll a, ll b) { return a * b % MOD; }

//HIGH11 大水题
//https://www.nowcoder.com/practice/6b9770de551c426287252421742f6ebf
//简单的递归

ll addnum(ll n) {
    ll newnum=0;
    while (n) {
        newnum+=n%10;
        n=n/10;
    }
    if (newnum>10) newnum=addnum(newnum);
    return newnum;
}
void solve() {
    ll n;
    cin >> n;
    cout<<addnum(n);

}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High12 小q的数列

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
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b) { return (a + b) % MOD; }
inline ll submod(ll a, ll b) { return (a - b + MOD) % MOD; }
inline ll mulmod(ll a, ll b) { return a * b % MOD; }

//HIGH12 小q的数列
//https://www.nowcoder.com/practice/8ea1e0d996f64e15961ae42e658a04a7
/*需要思路的题：
有两种方法：
1.递归找
2.位运算找
x大于等于2时，等同于x向右位移并加上2^0位置上的数，拆开分解其实就是x的二进制位的1的总和
*/

void solve() {
    ll n;
    cin >> n;
    ll ans=__builtin_popcountll(n);//注意这里的ll，没有会超范围
    cout<<ans<<' ';
    ll ans2=1;
    ans2=(1ll<<ans2)-1;
    cout<<ans2<<'\n';
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High13 括号匹配深度

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b) { return (a + b) % MOD; }
inline ll submod(ll a, ll b) { return (a - b + MOD) % MOD; }
inline ll mulmod(ll a, ll b) { return a * b % MOD; }

//HIGH13 括号匹配深度
//https://www.nowcoder.com/practice/a2d5b1875bb0408384278f40d1f236c9
/*
 *就是递归吧
 *好吧不递归也能做，遇到(就+1 遇到)就-1，每次+1判断是否为最大值就行了，
 *因为题目前提给的是一定合法
 *
 */

ll nowpos=0;

// ll getdeepth(string s) {
//     ll ans=1;
//     nowpos++;
//     while (s[nowpos]!=')'&&nowpos<s.size()) {
//         if (s[nowpos]=='(') {
//             ans+=getdeepth(s);
//         }
//     }
//     return ans;
// }
void solve() {
    string s;
    cin >> s;
    ll ans=0;
    ll temp=0;
    while (nowpos<s.length()) {

        if (s[nowpos]=='(') {
            temp++;
            ans=max(ans,temp);
        }else {
            temp--;
        }
        nowpos++;
    }
    cout << ans;

}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High14 斐波那契数列

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
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b) { return (a + b) % MOD; }
inline ll submod(ll a, ll b) { return (a - b + MOD) % MOD; }
inline ll mulmod(ll a, ll b) { return a * b % MOD; }

//HIGH14 斐波那契数列
//https://www.nowcoder.com/practice/c245af6cfdce49ceb5435f649ee14f89
/*
 *简单题，记得mod
 */
void solve() {
    ll k;
    cin >> k;
    ll f1=1,f2=1,f3=2;
    if (k<=2) {
        cout<<"1";
        return;
    }
    for (int i=3;i<=k;i++) {
        f3=addmod(f1,f2);
        f1=f2,f2=f3;
    }
    cout<<f3;

}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High15 计算阶乘

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
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b) { return (a + b) % MOD; }
inline ll submod(ll a, ll b) { return (a - b + MOD) % MOD; }
inline ll mulmod(ll a, ll b) { return a * b % MOD; }

//HIGH15 计算阶乘
//https://www.nowcoder.com/practice/b93729ad46d74a62801bdc320be2aa8e
/*
 *简单题，记得mod
 */
vector<ll> mp(1e6+7);
void init() {
    mp[1]=1;
    ll ans=1;
    for (ll i=2;i<=1e6;i++) {
        ans=mulmod(ans,i);
        mp[i]=ans;
    }
}
void solve() {
    ll n;
    cin >> n;
    cout<<mp[n]<<'\n';
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    init();
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High16 【模板】快速幂Ⅰ ‖ 模小整数

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b) { return (a + b) % MOD; }
inline ll submod(ll a, ll b) { return (a - b + MOD) % MOD; }
inline ll mulmod(ll a, ll b) { return a * b % MOD; }

//HIGH16 【模板】快速幂Ⅰ ‖ 模小整数
//https://www.nowcoder.com/practice/3d624107a6904da1bd0e8c9c85e17167
/*
 *快速幂
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}


void solve() {
    ll a,b,p;
    cin>>a>>b>>p;
    ll ans = fastPower(a,b,p);
    cout<<ans<<'\n';
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High17 【模板】分数取模

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH17 【模板】分数取模
//https://www.nowcoder.com/practice/23839ef20d5f4dbaa9664daa51864291
/*
 *快速幂
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}


void solve() {
    ll a,b,p=MOD;
    cin>>a>>b;
    // 将 a 转为模意义下的非负表示
    a = (a % MOD + MOD) % MOD;
    ll ans = divmod(a,b,p);
    cout<<ans<<'\n';
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High18 子数列求积

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH18 子数列求积
//https://www.nowcoder.com/practice/5daab034da954f5697dcf96c1808d34f
/*
 *前缀积
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}


void solve() {
    ll n,q;
    cin>>n>>q;
    vector<ll> v(n+1,0);
    vector<ll> qzj(n+1,1);
    for (ll i = 1; i <= n; i++) {
        cin>>v[i];
        qzj[i] = mulmod(v[i],qzj[i-1],MOD);
        //cout<<qzj[i]<<"!\n";
    }



    while (q--) {
        ll l,r;
        cin>>l>>r;
        ll ans=divmod(qzj[r],qzj[l-1],MOD);
        cout<<ans<<' ';
    }
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High19 好多次方

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH19 好多次方
//https://www.nowcoder.com/practice/8bf1186260634b209b5cff362da45305
/*
 *需要数论知识的一道题：费马小定理
 *a^(MOD−1)≡1(modMOD)。
 *我们可以通过这个定理来降幂
 *当MOD和a互质时 同余的结果总是按MOD-1循环的
 *因此我们对于很大的指数例如A^x拆成 A^(k*(MOD-1)+r)≡1^k×A^r=a^r(mod MOD)
 *总之对于得出对MOD取余的结果时，我们可以让指数对MOD-1取余再进行计算
 *
 *注意：对于算出指数为0的情况，改成MOD-1再计算更保险！
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}


void solve() {
    ll a,b,c;
    cin>>a>>b>>c;
    a%=MOD,b%=MOD,c%=MOD;
    ll pow=fastPower(b,c,MOD-1);
    if(pow==0) pow=MOD-1;
    ll ans=fastPower(a,pow,MOD);
    cout<<ans<<'\n';
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}