QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#640788#7996. 报数 IVucup-team3519#AC ✓122ms4028kbC++173.5kb2024-10-14 16:02:402024-10-14 16:02:40

Judging History

你现在查看的是最新测评结果

  • [2024-10-14 16:02:40]
  • 评测
  • 测评结果:AC
  • 用时:122ms
  • 内存:4028kb
  • [2024-10-14 16:02:40]
  • 提交

answer

#include <bits/stdc++.h>

template <int m>
class ModInt {
    int raw;
    using mint = ModInt;
    using i64 = int64_t;

public:
    ModInt() : raw(0) {}
    ModInt(const auto &v) {
        raw = v % m;
        if (raw < 0) {
            raw += m;
        }
    }
    int operator()() const {
        return raw;
    }

    mint &operator+=(const mint &rhs) {
        raw += rhs.raw;
        if (raw >= m) {
            raw -= m;
        }
        return *this;
    }
    mint &operator-=(const mint &rhs) {
        raw -= rhs.raw;
        if (raw < 0) {
            raw += m;
        }
        return *this;
    }
    mint &operator*=(const mint &rhs) {
        raw = (i64)raw * rhs.raw % m;
        return *this;
    }
    mint &operator/=(const mint &rhs) {
        return *this *= qpow(rhs, m - 2);
    }

    friend mint operator+(const mint &lhs, const mint &rhs) {
        return mint{lhs} += rhs;
    }
    friend mint operator-(const mint &lhs, const mint &rhs) {
        return mint{lhs} -= rhs;
    }
    friend mint operator*(const mint &lhs, const mint &rhs) {
        return mint{lhs} *= rhs;
    }
    friend mint operator/(const mint &lhs, const mint &rhs) {
        return mint{lhs} /= rhs;
    }

    static mint qpow(mint a, i64 b) {
        mint res = 1;
        while (b) {
            if (b & 1) {
                res *= a;
            }
            a *= a, b >>= 1;
        }
        return res;
    }
};

using mint = ModInt<static_cast<int>(1e9 + 7)>;

int mod(std::string s) {
    int res = 0;
    for (char c : s) {
        res += (c - '0');
    }
    return res % 9;
}
mint val(std::string s) {
    mint res = 0;
    for (char c : s) {
        res = res * 10 + (c - '0');
    }
    return res;
}

void solve() {
    std::string s;
    std::cin >> s;

    int k, m;
    std::cin >> k >> m;

    if (k >= 10) {
        if (m > 9) {
            std::cout << "0\n";
        } else {
            mint ans = val(s);
            int p = mod(s);
            std::cout << ((ans - p) / 9 + (p >= m))() << '\n';
        }
        return;
    }

    int sum = 0;
    std::vector<mint> g;
    for (char c : s) {
        int d = c - '0';
        
        std::vector<mint> ng(std::max<int>(sum + d, g.size() + 10));
        for (int i = 0; i < d; ++i) {
            ng[sum + i] += 1;
        }
        for (int i = 0; i < 10; ++i) {
            for (int x = 0; x < g.size(); ++x) {
                ng[x + i] += g[x];
            }
        }
        sum += d;

        g.swap(ng);
        while (!g.empty() && g.back()() == 0) {
            g.pop_back();
        }
    }

    if (g.size() < sum + 1) {
        g.resize(sum + 1);
    }
    g[sum] += 1;
    g[0] -= 1;

    auto f = [](int x) {
        int res = 0;
        while (x) {
            res += x % 10;
            x /= 10;
        }
        return res;
    };
    for (int i = 1; i <= k - 1; ++i) {
        std::vector<mint> ng(g.size());

        for (int x = 0; x < g.size(); ++x) {
            ng[f(x)] += g[x];
        }

        g.swap(ng);
        while (!g.empty() && g.back()() == 0) {
            g.pop_back();
        }
    }

    if (g.size() < m + 1) {
        std::cout << "0\n";
    } else {
        std::cout << g[m]() << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3804kb

input:

2
114 1 5
514 2 10

output:

8
10

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

5
114 1 5
514 2 10
114514 3 7
1919810 2 13
1145141919810114514191981011451419198101145141919810114514191981011451419198101145141919810114514191981011451419198101145141919810 1 79

output:

8
10
12724
504
481046284

result:

ok 5 lines

Test #3:

score: 0
Accepted
time: 116ms
memory: 3784kb

input:

5
3134666912140933323880320519044791121794814671711104987304374190280064994554822259889216567113228716903875026053927191961850586115167336109747673868148288830282192461669674173201533887392623483710043038941036243583011049049915834937139438028987629569618561762595613799223807979488245056374812076511...

output:

0
613343513
0
500149787
932367667

result:

ok 5 lines

Test #4:

score: 0
Accepted
time: 117ms
memory: 3728kb

input:

5
1139519997005658838804233882542131329603951012645222504700958241682545257324091070752720569220022637054777343187779232016568942045167801853025395316038491270541841827939668031807503056209394655628349207403327386083909984082879989255237547274110143051980886947606735206241362546384481120301780245959...

output:

0
0
983106233
842410978
351127737

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 117ms
memory: 3780kb

input:

5
8638076091316635855641492966551052879887835736093039980247820372626975300011595185556660107638347885877620156412525017113706895612406460047827904025826640853053762221239009476530804397983925491363476392003741370633988524528072186299564325622601218035310613510134479162974878452692502169127286160440...

output:

0
151494485
491996396
951216080
735591005

result:

ok 5 lines

Test #6:

score: 0
Accepted
time: 117ms
memory: 4028kb

input:

5
4594403190887655851098979323885347301970260472182981436563110607463337770897498592230279433635011809482497666151819612860549852933087582131069399973150048275594755688227873941703801791577493672811179138154635173296855021815570777969295164438906410283251071005981539590431740858876880832337309525533...

output:

452162993
993032288
529250142
0
0

result:

ok 5 lines

Test #7:

score: 0
Accepted
time: 113ms
memory: 3780kb

input:

5
7106329661074460076851813089444392472728206874451143771638786962963099120130351553150316525985245033972323999641553983578568333846746709032264525531367915930983812069660457027974526824268427908058438462283103774963889147187903776098321357665707620452891363086885353145154955480116362167820560099473...

output:

0
42143665
0
0
266635325

result:

ok 5 lines

Test #8:

score: 0
Accepted
time: 115ms
memory: 3724kb

input:

5
3197096843267069616758413776891049764649182364659681310636123435063129351340319661216252795154685419993835505771367978692486745621757064307866143997529010856187698866761085397967488612326286182291301655780420802213700700872824442868225191222911023750488609973480926167606063152176688092948837104972...

output:

447917122
738150576
134709012
571675718
0

result:

ok 5 lines

Test #9:

score: 0
Accepted
time: 116ms
memory: 3780kb

input:

5
7612942550467855237767978070830743429305395120370014044416141696259440200835613011108477499855450341979327882148431400498007877975643997499046007388707405687392636406520850657394581417406913024784851871291661719356877660941151602720564069428677800545614776632869404791295787921432277016643912651129...

output:

0
264129072
541216127
357954287
0

result:

ok 5 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

5
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

output:

0
0
0
0
0

result:

ok 5 lines

Test #11:

score: 0
Accepted
time: 118ms
memory: 3928kb

input:

5
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

output:

910755804
259808709
937821856
357970005
357970004

result:

ok 5 lines

Test #12:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

5
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0
0
0
0
0

result:

ok 5 lines

Test #13:

score: 0
Accepted
time: 116ms
memory: 3728kb

input:

5
5493600942860040477621631776833866796633825984175588516360787148451695869301784861251377693592220895430016092915864584070561727072786074401876239679966435830840108325415158767012889770532442098922126012279790947926699687673153716303479935588263453954268774120993175103389470374955885050132475090943...

output:

0
300754613
527108222
803186040
892721871

result:

ok 5 lines

Test #14:

score: 0
Accepted
time: 118ms
memory: 3700kb

input:

5
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

320215386
716889023
567624008
357970005
357970006

result:

ok 5 lines

Test #15:

score: 0
Accepted
time: 116ms
memory: 3720kb

input:

5
9812761167325920856130376846862436937947447230654673184010669691739766031552475237221268849030438467080297886603870858917934654394088222131015941324484064243169674411393827605062172844413306867153409653032875875932730337155928621241642891239404177544951325020506663647342309917196598863243062161544...

output:

0
469928597
497418961
0
391423761

result:

ok 5 lines

Test #16:

score: 0
Accepted
time: 116ms
memory: 3728kb

input:

5
9013501952727330363984611655757069529140061668352243348131242141715906906114807898855698384965618856928927417081394644166161162830825179502161401400642096135223979387761058683717466953382929504725324258978052930668420706866257850069631732579721803675116406468720025921542594305209295461027074284529...

output:

385295755
0
826010110
468568966
0

result:

ok 5 lines

Test #17:

score: 0
Accepted
time: 117ms
memory: 3720kb

input:

5
8299276307146554536050575918961724216373725603114732403143797725790612708959386530057274467495195402828666463169527607000394687018773329311746262289704318815996536046048237937697238691975566621555830914989783566285006290394230091450543627201211538144590398957372070315341068147825604925011592907516...

output:

0
510867977
0
343376120
214886107

result:

ok 5 lines

Test #18:

score: 0
Accepted
time: 116ms
memory: 3784kb

input:

5
5978386495534656451410085599244329473463314859713321863671010880820574367293215984254435511977274737538376669406905970846704986107233076928078383576465358933281714235428695844731759396130287355362520342786149980212289046796827813545285558877894772706667916112882424152831253823242761178245591040551...

output:

200381997
248732590
659988610
728803841
281731921

result:

ok 5 lines

Test #19:

score: 0
Accepted
time: 122ms
memory: 4020kb

input:

5
3653745784886652871154357862309923857817567252560725002381570519161248252147392315049190794174402649782040388482129025970204654043850249370372033244471538178164319261755776547097203201498608147530621634820597155316537832780268365695458704201328436275425247055333335893078213722495376788491166394840...

output:

0
827622189
909406252
224192882
472231991

result:

ok 5 lines

Test #20:

score: 0
Accepted
time: 117ms
memory: 3672kb

input:

5
8033033272391208112504025738196814953295344818136472894597554051040020955286362518341894063333412258812817219386808976514037940329057156352396807896773931916676875163079204283714827821854630201268421360605246824369120510639882686009186217462096143084170888173631995492474470043432451899005431488434...

output:

210535726
822079653
985955681
540372548
893241037

result:

ok 5 lines

Test #21:

score: 0
Accepted
time: 117ms
memory: 4016kb

input:

5
5567143473825105413062640204906776053975645715210961093621242820515284746059383788299405075430487954445602098969989027355660374546878999126847721403752212660945084700687121976823655410921184811436776882931203119629438066770465897899783553110960619700314302907304525788754873835497787674395031347966...

output:

0
0
358266018
0
50998365

result:

ok 5 lines