CSES - Aalto Competitive Programming 2024 - wk11 - Mon - Results
Submission details
Task:Skittles
Sender:Rasse
Submission time:2024-11-18 17:49:22 +0200
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#10.85 sdetails
#20.85 sdetails
#30.85 sdetails
#40.85 sdetails
#50.85 sdetails
#60.85 sdetails
#70.85 sdetails
#80.85 sdetails
#90.85 sdetails
#100.85 sdetails
#110.85 sdetails
#120.83 sdetails
#130.73 sdetails
#140.79 sdetails
#150.80 sdetails
#160.80 sdetails
#170.78 sdetails
#180.73 sdetails
#190.82 sdetails
#200.74 sdetails
#210.84 sdetails
#220.74 sdetails
#230.85 sdetails
#240.80 sdetails
#250.83 sdetails
#260.84 sdetails
#270.82 sdetails
#280.82 sdetails
#290.77 sdetails
#300.75 sdetails
#310.83 sdetails
#320.81 sdetails
#330.83 sdetails
#340.83 sdetails
#350.78 sdetails
#360.76 sdetails
#370.80 sdetails
#380.75 sdetails
#390.82 sdetails
#400.81 sdetails
#410.78 sdetails
#420.78 sdetails
#430.84 sdetails
#440.78 sdetails
#450.84 sdetails
#460.83 sdetails
#470.84 sdetails
#480.75 sdetails
#490.79 sdetails
#500.83 sdetails
#510.76 sdetails
#520.76 sdetails
#530.73 sdetails
#540.84 sdetails
#550.75 sdetails
#560.75 sdetails
#570.74 sdetails
#580.75 sdetails
#590.79 sdetails
#600.74 sdetails
#610.76 sdetails
#620.78 sdetails
#630.74 sdetails

Compiler report

input/code.cpp: In function 'long long int initNCR(long long int, long long int)':
input/code.cpp:70:1: warning: no return statement in function returning non-void [-Wreturn-type]
   70 | }
      | ^

Code

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <queue>
#include <climits>
#include <cmath>
#include <functional>
#include <type_traits>
#include <fstream>
#include <bitset>
#include <complex>
#include <iomanip>

#include <ext/pb_ds/assoc_container.hpp> // gcc only
template<typename T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
 
#define int long long
using namespace std;
 
#define cross(x, y) (((x)*conj(y)).imag())
#define sign(v) ((0 < (v)) - ((v) < 0))


int mod = 998244353;

int p(int a, int b, int m)
{
    if (b == 0) return 1;
    else if (b % 2 == 0) { int r = p(a, b/2, m); return (r*r) % m; }
    else return (p(a, b-1, m)*a) % m; 
}
int gdc(int a, int b)
{
    if (b == 0) return a;
    return gdc(b, a%b);
}
 
// Works to approx n=60

vector<int> facts;
int startInverse = 1;

int initNCR(int r, int maxN)
{
    facts = vector<int>(maxN+1);
    facts[0] = 1;
    int multiple = 1;
    for (int i = 1; i <= r; i++)
    {
        multiple *= i;
        multiple %= mod;
    }
    facts[r] = multiple;
    for (int i = r+1; i < maxN; i++)
    {
        multiple *= i;
        multiple %= mod;
        multiple *= p(i-r, mod-2, mod);
        multiple %= mod;

        facts[i] = multiple;
    }
}

int fastNCR(int n, int r)
{
    int val = startInverse * facts[n];
    val %= mod;
    return val * p(facts[r], mod-2, mod);
}

int nCr(int n, int r)
{
    int res = 1;
    for (int i = 0; i < r; i++)
    {
        res *= (n-i);
        res *= p(i+1, mod-2, mod);
    }
    return res;
}



void solve()
{
    int n, a, b;
    cin >> n >> a >> b;

    initNCR(n-1, 700010);

    int result = 0;

    for (int i = a; i <= b; i++)
    {
        result += fastNCR(i+n-1, n-1);
        result %= mod;
    }
    cout << result;

}
 
 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(15);
 
    int t = 1;
 
    //cin >> t;
 
    for (int i = 0; i < t; i++)
    {
        solve();
        //cout.flush();
    }
}

Test details

Test 1

Verdict:

input
1 1 10

correct output
10

user output
(empty)

Test 2

Verdict:

input
2 3 3

correct output
4

user output
(empty)

Test 3

Verdict:

input
2 4 5

correct output
11

user output
(empty)

Test 4

Verdict:

input
3 4 5

correct output
36

user output
(empty)

Test 5

Verdict:

input
3 2 2

correct output
6

user output
(empty)

Test 6

Verdict:

input
5 5 5

correct output
126

user output
(empty)

Test 7

Verdict:

input
10 10 10

correct output
92378

user output
(empty)

Test 8

Verdict:

input
10 1 10

correct output
184755

user output
(empty)

Test 9

Verdict:

input
100 100 100

correct output
866655715

user output
(empty)

Test 10

Verdict:

input
10 100 100

correct output
918123961

user output
(empty)

Test 11

Verdict:

input
1000 10 10

correct output
84965120

user output
(empty)

Test 12

Verdict:

input
10000 10000 10000

correct output
658363258

user output
(empty)

Test 13

Verdict:

input
100000 100000 100000

correct output
966937032

user output
(empty)

Test 14

Verdict:

input
54883 59286 71521

correct output
908996595

user output
(empty)

Test 15

Verdict:

input
41703 72034 99721

correct output
139159644

user output
(empty)

Test 16

Verdict:

input
43601 2593 18509

correct output
804369499

user output
(empty)

Test 17

Verdict:

input
55081 7073 70816

correct output
806880502

user output
(empty)

Test 18

Verdict:

input
96705 54725 90064

correct output
521461113

user output
(empty)

Test 19

Verdict:

input
22200 5519 87075

correct output
866679044

user output
(empty)

Test 20

Verdict:

input
89288 33199 94750

correct output
812654801

user output
(empty)

Test 21

Verdict:

input
7631 22735 77994

correct output
30255908

user output
(empty)

Test 22

Verdict:

input
87345 1112 96856

correct output
944788802

user output
(empty)

Test 23

Verdict:

input
1038 36447 50189

correct output
654272260

user output
(empty)

Test 24

Verdict:

input
41703 72034 99721

correct output
139159644

user output
(empty)

Test 25

Verdict:

input
18028 1948 6831

correct output
631722506

user output
(empty)

Test 26

Verdict:

input
4873 28912 79929

correct output
106074189

user output
(empty)

Test 27

Verdict:

input
28606 2900 95813

correct output
538554734

user output
(empty)

Test 28

Verdict:

input
25093 4610 68059

correct output
799962519

user output
(empty)

Test 29

Verdict:

input
67575 4472 32712

correct output
857647130

user output
(empty)

Test 30

Verdict:

input
82449 18136 86245

correct output
420446937

user output
(empty)

Test 31

Verdict:

input
18558 38661 75914

correct output
924425479

user output
(empty)

Test 32

Verdict:

input
35543 34086 47960

correct output
210554536

user output
(empty)

Test 33

Verdict:

input
20101 32903 99080

correct output
88647511

user output
(empty)

Test 34

Verdict:

input
18028 1948 6831

correct output
631722506

user output
(empty)

Test 35

Verdict:

input
61218 12076 16908

correct output
820171450

user output
(empty)

Test 36

Verdict:

input
78139 13111 69284

correct output
904117059

user output
(empty)

Test 37

Verdict:

input
45455 2862 43952

correct output
430742811

user output
(empty)

Test 38

Verdict:

input
84538 61888 77158

correct output
294818599

user output
(empty)

Test 39

Verdict:

input
26937 59685 80971

correct output
680140546

user output
(empty)

Test 40

Verdict:

input
30632 9727 88573

correct output
877318826

user output
(empty)

Test 41

Verdict:

input
55737 66074 71002

correct output
123569267

user output
(empty)

Test 42

Verdict:

input
59351 587 51636

correct output
122513346

user output
(empty)

Test 43

Verdict:

input
8954 7866 51810

correct output
961929284

user output
(empty)

Test 44

Verdict:

input
61218 12076 16908

correct output
820171450

user output
(empty)

Test 45

Verdict:

input
9556 43003 92502

correct output
424034313

user output
(empty)

Test 46

Verdict:

input
20433 945 23474

correct output
794687216

user output
(empty)

Test 47

Verdict:

input
9941 45344 78340

correct output
875489658

user output
(empty)

Test 48

Verdict:

input
82532 68582 70655

correct output
238007640

user output
(empty)

Test 49

Verdict:

input
52729 37586 66259

correct output
93243919

user output
(empty)

Test 50

Verdict:

input
10475 17392 24871

correct output
977605482

user output
(empty)

Test 51

Verdict:

input
76232 88012 95143

correct output
871309467

user output
(empty)

Test 52

Verdict:

input
77184 58424 64500

correct output
693972156

user output
(empty)

Test 53

Verdict:

input
96888 47083 55295

correct output
406195062

user output
(empty)

Test 54

Verdict:

input
9556 43003 92502

correct output
424034313

user output
(empty)

Test 55

Verdict:

input
83891 47894 87748

correct output
686766192

user output
(empty)

Test 56

Verdict:

input
85080 21779 92819

correct output
114946782

user output
(empty)

Test 57

Verdict:

input
88235 6779 56603

correct output
70147249

user output
(empty)

Test 58

Verdict:

input
88858 66896 98375

correct output
601764178

user output
(empty)

Test 59

Verdict:

input
50586 8901 76084

correct output
881324074

user output
(empty)

Test 60

Verdict:

input
87594 26882 34225

correct output
42681251

user output
(empty)

Test 61

Verdict:

input
73130 30310 55103

correct output
843664756

user output
(empty)

Test 62

Verdict:

input
63584 31874 92876

correct output
437812641

user output
(empty)

Test 63

Verdict:

input
88714 2531 74051

correct output
603847190

user output
(empty)