1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

void solve(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<(a+b+c)*d;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    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

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=k;i++)cout<<"1";
    for(int i=k+1;i<=n;i++)cout<<"4";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    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
39

#include <bits/stdc++.h>
using namespace std;
#define ls now << 1
#define rs now << 1 | 1
#define endl "\n"
#define lowbit(x) ((x) & (-x))
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    vector<int> s(4, 0);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s[x]++;
    }
    int ans = 1e9;
    for (int i = 0; i < 4; i++) {
        int res = s[i] + s[(i + 1) % 4] * 2 + s[(i + 2) % 4] * 3;
        int m = (res + i + 3) % 4;
        if (m != 0)
            ans = min(ans, res + 4 - m);
        else
            ans = min(ans, res);
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--) solve();
    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
39
40

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;


void solve(){
    int n,k;
    double r0,c0,p,L,R;
    cin>>n>>k>>r0>>c0>>p>>L>>R;
    double ans=0;
    vector<double> r(n+1, 0), c(n+1, 0);
    r[0]=r0;
    c[0]=c0;
    for(int i=1;i<=k;i++){
        int pos;
        double val;
        cin>>pos>>val;
        r[pos]=val;
    }
    for(int i=1;i<=n;i++){
        if(r[i]==0)r[i]=L;
        c[i]=p*c[i-1]+(1-p)*r[i-1];
        ans+=(c[i]-r[i]);
    }
    cout<<fixed<<setprecision(10)<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    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
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

#include <bits/stdc++.h>
using namespace std;
#define ls now << 1
#define rs now << 1 | 1
#define endl "\n"
#define lowbit(x) ((x) & (-x))
typedef long long ll;
const int N = 1e5 + 7, mod = 998244353;

ll jc[N], inv[N];

ll qpow(ll x, ll k) {
    ll ans = 1, tmp = x;
    while (k) {
        if (k & 1) ans = ans * tmp % mod;
        tmp = tmp * tmp % mod;
        k >>= 1;
    }
    return ans;
}
ll C(int x, int y) {
    if (x < y) return 0;
    return jc[x] * inv[y] % mod * inv[x - y] % mod;
}

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> pos;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            pos.push_back(i);
        }
    }
    if (pos.size() < k) {
        cout << 0 << endl;
        return;
    }
    pos.push_back(n);
    ll ans = 0;
    ans = C(pos[k], k);
    for (int i = k; i + 1 < pos.size(); i++) {
        ans = (ans + C(pos[i+1] - pos[i - k] - 1, k)) % mod;
        ans = (ans + mod - max(1ll, C(pos[i] - pos[i - k] - 1, k - 1))) % mod;
    }
    cout << ans % mod << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    inv[0] = jc[0] = 1;
    for (int i = 1; i < N; ++i) {
        jc[i] = jc[i - 1] * i % mod;
    }
    inv[N - 1] = qpow(jc[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; --i) {
        inv[i] = inv[i + 1] * (i + 1) % mod;  // O(N) 线性逆元
    }
    int t = 1;
    cin >> t;
    while (t--) solve();
    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
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

#include <bits/stdc++.h>
using namespace std;
#define ls now << 1
#define rs now << 1 | 1
#define endl "\n"
#define lowbit(x) ((x) & (-x))
typedef long long ll;
const int N = 1e5 + 7, mod = 998244353;

int p[N][2][4];
int ans;
int n, a, b, c;
map<int, int> mp;

void sol (int x) {
    vector<int> v, s(n*2+10, 0);
    for (int i = 0; i < n; i++) {
        v.push_back(p[i][0][x]);
        v.push_back(p[i][1][x]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int tot = 0;
    for (auto x : v) {
        mp[x] = tot++;
    }
    for (int i = 0; i < n; i++) {
        if(p[i][0][x] > p[i][1][x])swap(p[i][0][x], p[i][1][x]);
        s[mp[p[i][0][x]]]++;
        s[mp[p[i][1][x]] + 1]--;
    }
    for (int i = 1; i < s.size(); i++) {
        s[i] += s[i - 1];
    }
    for (auto x : s) ans = max(ans, x);
}

void solve() {
    cin >> n >> a >> b >> c;
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        p[i][0][0] = x;
        p[i][0][1] = y;
        p[i][0][2] = z;
        cin >> x >> y >> z;
        p[i][1][0] = x;
        p[i][1][1] = y;
        p[i][1][2] = z;
    }
    for(int i = 0; i < 3; i++) {
        sol(i);
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <bits/stdc++.h>
using namespace std;
#define ls now << 1
#define rs now << 1 | 1
#define endl "\n"
#define lowbit(x) ((x) & (-x))
typedef long long ll;
const int N = 1e5 + 7, mod = 998244353, inf = 1e9 + 7;

struct Node {
    int to, w;
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<Node>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    vector<vector<ll>> f(40, vector<ll>(n + 1, -1));
    for (int i = 1; i <= n; i++) f[0][i] = 1;
    for (int i = 1; i < 40; i++) {
        for (int j = 1; j <= n; j++) {
            for (auto [u,w] : g[j]) {
                if (f[i - 1][u] == -1)continue;
                ll tmp = f[i-1][u] * w;
                if (tmp > inf) tmp = inf;
                f[i][j] = max(f[i][j], tmp);
            }
        }
    }
    while (q--) {
        ll p, x;
        cin >> p >> x;
        int ans = -1;
        for(int i = 1; i < 40; i++) {
            if(f[i][p] == -1) break;
            if(f[i][p] > x) {
                ans = i;
                break;
            }
        }
        cout << ans << endl;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    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
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int n, k, q, blk;
string s;
vector<array<int, 26>> hs;
vector<pair<ll, ll>> hval;
vector<int> hid;
ll ans;
const ll M1 = 1e9 + 7;
const ll M2 = 1e9 + 9;
const ll B1 = 911;
const ll B2 = 3571;

pair<ll, ll> hsh(const array<int, 26>& a) {
    ll h1 = 0, h2 = 0;
    for (int i = 0; i < 26; ++i) {
        h1 = (h1 * B1 + a[i]) % M1;
        h2 = (h2 * B2 + a[i]) % M2;
    }
    return {h1, h2};
}

struct Q {
    int l, r, id;
    bool operator<(const Q &o) const {
        int bl = l / blk, br = o.l / blk;
        if (bl != br) return bl < br;
        return (bl & 1) ? r < o.r : r > o.r;
    }
};

vector<int> cnt;

void add(int x) {
    int id = hid[x];
    ans += cnt[id];
    cnt[id]++;
}

void del(int x) {
    int id = hid[x];
    cnt[id]--;
    ans -= cnt[id];
}

void run() {
    cin >> n >> k >> q;
    cin >> s;
    s = " " + s;
    blk = sqrt(n) + 1;
    hs.resize(n + 1);
    hs[0].fill(0);
    for (int i = 1; i <= n; i++) {
        hs[i] = hs[i - 1];
        hs[i][s[i] - 'a'] = (hs[i][s[i] - 'a'] + 1) % k;
    }
    hval.resize(n + 1);
    for (int i = 0; i <= n; i++) hval[i] = hsh(hs[i]);
    vector<pair<ll, ll>> all = hval;
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    auto get = [&](pair<ll, ll> h) {
        return lower_bound(all.begin(), all.end(), h) - all.begin();
    };
    hid.resize(n + 1);
    for (int i = 0; i <= n; ++i) hid[i] = get(hval[i]);
    vector<Q> qry(q);
    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        qry[i] = {x - 1, y, i};
    }
    sort(qry.begin(), qry.end());
    vector<ll> res(q);
    cnt.assign(all.size(), 0);
    int L = 0, R = -1;
    ans = 0;
    for (auto [l, r, id] : qry) {
        while (R < r) add(++R);
        while (R > r) del(R--);
        while (L < l) del(L++);
        while (L > l) add(--L);
        res[id] = ans;
    }
    for (auto x : res) cout << x << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    run();
    return 0;
}