結果
| 問題 | No.148 試験監督（3） |
| ユーザー |
 Yang33
|
| 提出日時 | 2018-05-04 20:34:56 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 100 ms / 1,000 ms |
| コード長 | 14,557 bytes |
| コンパイル時間 | 1,695 ms |
| コンパイル使用メモリ | 171,168 KB |
| 実行使用メモリ | 4,380 KB |
| 最終ジャッジ日時 | 2023-09-10 09:46:55 |
| 合計ジャッジ時間 | 3,321 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 26 ms
4,380 KB |
| testcase_01 | AC | 35 ms
4,380 KB |
| testcase_02 | AC | 85 ms
4,380 KB |
| testcase_03 | AC | 95 ms
4,376 KB |
| testcase_04 | AC | 100 ms
4,380 KB |
| testcase_05 | AC | 74 ms
4,380 KB |
| testcase_06 | AC | 57 ms
4,380 KB |
| testcase_07 | AC | 92 ms
4,376 KB |
| testcase_08 | AC | 77 ms
4,376 KB |
| testcase_09 | AC | 5 ms
4,376 KB |
| testcase_10 | AC | 5 ms
4,376 KB |
| testcase_11 | AC | 2 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using VS = vector<string>; using LL = long long;
using VI = vector<int>; using VVI = vector<VI>;
using PII = pair<int, int>; using PLL = pair<LL, LL>;
using VL = vector<LL>; using VVL = vector<VL>;
#define ALL(a) begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9; const LL LINF = 1e16;
const LL MOD = 1000000007; const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 }; int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
/* ----- 2018/05/03 Problem: yukicoder 148 / Link: http://yukicoder.me/problems/no/148 ----- */
/* ------問題------
-----問題ここまで----- */
/* -----解説等-----
nCr(C-P+1,P)
----解説ここまで---- */
PII f(string& s) {
LL ret = 0;
int over = 0;
FOR(i, 0, SZ(s)) {
ret *= 10;
ret += s[i] - '0';
if (ret >= MOD) {
over = 1;
}
ret %= MOD;
}
return PII(ret, over);
}
const long long mod = 1e9 + 7;
long long modpow(long long a, long long b) { //a==0の処理は問題次第
if (b == 0) return 1;
return modpow(a * a % mod, b / 2) * (b & 1 ? a : 1) % mod;
}
long long modinv(long long a) {
return modpow(a, mod - 2);
}
vector<long long> fact, inv_fact;
void init_fact(int n) {
fact.resize(n);
fact[0] = 1;
for (int i = 1; i < n; i++) {
fact[i] = i * fact[i - 1] % mod;
}
}
LL factume[] = {
1,
641102369,
578095319,
5832229,
259081142,
974067448,
316220877,
690120224,
251368199,
980250487,
682498929,
134623568,
95936601,
933097914,
167332441,
598816162,
336060741,
248744620,
626497524,
288843364,
491101308,
245341950,
565768255,
246899319,
968999,
586350670,
638587686,
881746146,
19426633,
850500036,
76479948,
268124147,
842267748,
886294336,
485348706,
463847391,
544075857,
898187927,
798967520,
82926604,
723816384,
156530778,
721996174,
299085602,
323604647,
172827403,
398699886,
530389102,
294587621,
813805606,
67347853,
497478507,
196447201,
722054885,
228338256,
407719831,
762479457,
746536789,
811667359,
778773518,
27368307,
438371670,
59469516,
5974669,
766196482,
606322308,
86609485,
889750731,
340941507,
371263376,
625544428,
788878910,
808412394,
996952918,
585237443,
1669644,
361786913,
480748381,
595143852,
837229828,
199888908,
526807168,
579691190,
145404005,
459188207,
534491822,
439729802,
840398449,
899297830,
235861787,
888050723,
656116726,
736550105,
440902696,
85990869,
884343068,
56305184,
973478770,
168891766,
804805577,
927880474,
876297919,
934814019,
676405347,
567277637,
112249297,
44930135,
39417871,
47401357,
108819476,
281863274,
60168088,
692636218,
432775082,
14235602,
770511792,
400295761,
697066277,
421835306,
220108638,
661224977,
261799937,
168203998,
802214249,
544064410,
935080803,
583967898,
211768084,
751231582,
972424306,
623534362,
335160196,
243276029,
554749550,
60050552,
797848181,
395891998,
172428290,
159554990,
887420150,
970055531,
250388809,
487998999,
856259313,
82104855,
232253360,
513365505,
244109365,
1559745,
695345956,
261384175,
849009131,
323214113,
747664143,
444090941,
659224434,
80729842,
570033864,
664989237,
827348878,
195888993,
576798521,
457882808,
731551699,
212938473,
509096183,
827544702,
678320208,
677711203,
289752035,
66404266,
555972231,
195290384,
97136305,
349551356,
785113347,
83489485,
66247239,
52167191,
307390891,
547665832,
143066173,
350016754,
917404120,
296269301,
996122673,
23015220,
602139210,
748566338,
187348575,
109838563,
574053420,
105574531,
304173654,
542432219,
34538816,
325636655,
437843114,
630621321,
26853683,
933245637,
616368450,
238971581,
511371690,
557301633,
911398531,
848952161,
958992544,
925152039,
914456118,
724691727,
636817583,
238087006,
946237212,
910291942,
114985663,
492237273,
450387329,
834860913,
763017204,
368925948,
475812562,
740594930,
45060610,
806047532,
464456846,
172115341,
75307702,
116261993,
562519302,
268838846,
173784895,
243624360,
61570384,
481661251,
938269070,
95182730,
91068149,
115435332,
495022305,
136026497,
506496856,
710729672,
113570024,
366384665,
564758715,
270239666,
277118392,
79874094,
702807165,
112390913,
730341625,
103056890,
677948390,
339464594,
167240465,
108312174,
839079953,
479334442,
271788964,
135498044,
277717575,
591048681,
811637561,
353339603,
889410460,
839849206,
192345193,
736265527,
316439118,
217544623,
788132977,
618898635,
183011467,
380858207,
996097969,
898554793,
335353644,
54062950,
611251733,
419363534,
965429853,
160398980,
151319402,
990918946,
607730875,
450718279,
173539388,
648991369,
970937898,
500780548,
780122909,
39052406,
276894233,
460373282,
651081062,
461415770,
358700839,
643638805,
560006119,
668123525,
686692315,
673464765,
957633609,
199866123,
563432246,
841799766,
385330357,
504962686,
954061253,
128487469,
685707545,
299172297,
717975101,
577786541,
318951960,
773206631,
306832604,
204355779,
573592106,
30977140,
450398100,
363172638,
258379324,
472935553,
93940075,
587220627,
776264326,
793270300,
291733496,
522049725,
579995261,
335416359,
142946099,
472012302,
559947225,
332139472,
499377092,
464599136,
164752359,
309058615,
86117128,
580204973,
563781682,
954840109,
624577416,
895609896,
888287558,
836813268,
926036911,
386027524,
184419613,
724205533,
403351886,
715247054,
716986954,
830567832,
383388563,
68409439,
6734065,
189239124,
68322490,
943653305,
405755338,
811056092,
179518046,
825132993,
343807435,
985084650,
868553027,
148528617,
160684257,
882148737,
591915968,
701445829,
529726489,
302177126,
974886682,
241107368,
798830099,
940567523,
11633075,
325334066,
346091869,
115312728,
473718967,
218129285,
878471898,
180002392,
699739374,
917084264,
856859395,
435327356,
808651347,
421623838,
105419548,
59883031,
322487421,
79716267,
715317963,
429277690,
398078032,
316486674,
384843585,
940338439,
937409008,
940524812,
947549662,
833550543,
593524514,
996164327,
987314628,
697611981,
636177449,
274192146,
418537348,
925347821,
952831975,
893732627,
1277567,
358655417,
141866945,
581830879,
987597705,
347046911,
775305697,
125354499,
951540811,
247662371,
343043237,
568392357,
997474832,
209244402,
380480118,
149586983,
392838702,
309134554,
990779998,
263053337,
325362513,
780072518,
551028176,
990826116,
989944961,
155569943,
596737944,
711553356,
268844715,
451373308,
379404150,
462639908,
961812918,
654611901,
382776490,
41815820,
843321396,
675258797,
845583555,
934281721,
741114145,
275105629,
666247477,
325912072,
526131620,
252551589,
432030917,
554917439,
818036959,
754363835,
795190182,
909210595,
278704903,
719566487,
628514947,
424989675,
321685608,
50590510,
832069712,
198768464,
702004730,
99199382,
707469729,
747407118,
302020341,
497196934,
5003231,
726997875,
382617671,
296229203,
183888367,
703397904,
552133875,
732868367,
350095207,
26031303,
863250534,
216665960,
561745549,
352946234,
784139777,
733333339,
503105966,
459878625,
803187381,
16634739,
180898306,
68718097,
985594252,
404206040,
749724532,
97830135,
611751357,
31131935,
662741752,
864326453,
864869025,
167831173,
559214642,
718498895,
91352335,
608823837,
473379392,
385388084,
152267158,
681756977,
46819124,
313132653,
56547945,
442795120,
796616594,
256141983,
152028387,
636578562,
385377759,
553033642,
491415383,
919273670,
996049638,
326686486,
160150665,
141827977,
540818053,
693305776,
593938674,
186576440,
688809790,
565456578,
749296077,
519397500,
551096742,
696628828,
775025061,
370732451,
164246193,
915265013,
457469634,
923043932,
912368644,
777901604,
464118005,
637939935,
956856710,
490676632,
453019482,
462528877,
502297454,
798895521,
100498586,
699767918,
849974789,
811575797,
438952959,
606870929,
907720182,
179111720,
48053248,
508038818,
811944661,
752550134,
401382061,
848924691,
764368449,
34629406,
529840945,
435904287,
26011548,
208184231,
446477394,
206330671,
366033520,
131772368,
185646898,
648711554,
472759660,
523696723,
271198437,
25058942,
859369491,
817928963,
330711333,
724464507,
437605233,
701453022,
626663115,
281230685,
510650790,
596949867,
295726547,
303076380,
465070856,
272814771,
538771609,
48824684,
951279549,
939889684,
564188856,
48527183,
201307702,
484458461,
861754542,
326159309,
181594759,
668422905,
286273596,
965656187,
44135644,
359960756,
936229527,
407934361,
267193060,
456152084,
459116722,
124804049,
262322489,
920251227,
816929577,
483924582,
151834896,
167087470,
490222511,
903466878,
361583925,
368114731,
339383292,
388728584,
218107212,
249153339,
909458706,
322908524,
202649964,
92255682,
573074791,
15570863,
94331513,
744158074,
196345098,
334326205,
9416035,
98349682,
882121662,
769795511,
231988936,
888146074,
137603545,
582627184,
407518072,
919419361,
909433461,
986708498,
310317874,
373745190,
263645931,
256853930,
876379959,
702823274,
147050765,
308186532,
175504139,
180350107,
797736554,
606241871,
384547635,
273712630,
586444655,
682189174,
666493603,
946867127,
819114541,
502371023,
261970285,
825871994,
126925175,
701506133,
314738056,
341779962,
561011609,
815463367,
46765164,
49187570,
188054995,
957939114,
64814326,
933376898,
329837066,
338121343,
765215899,
869630152,
978119194,
632627667,
975266085,
435887178,
282092463,
129621197,
758245605,
827722926,
201339230,
918513230,
322096036,
547838438,
985546115,
852304035,
593090119,
689189630,
555842733,
567033437,
469928208,
212842957,
117842065,
404149413,
155133422,
663307737,
208761293,
206282795,
717946122,
488906585,
414236650,
280700600,
962670136,
534279149,
214569244,
375297772,
811053196,
922377372,
289594327,
219932130,
211487466,
701050258,
398782410,
863002719,
27236531,
217598709,
375472836,
810551911,
178598958,
247844667,
676526196,
812283640,
863066876,
857241854,
113917835,
624148346,
726089763,
564827277,
826300950,
478982047,
439411911,
454039189,
633292726,
48562889,
802100365,
671734977,
945204804,
508831870,
398781902,
897162044,
644050694,
892168027,
828883117,
277714559,
713448377,
624500515,
590098114,
808691930,
514359662,
895205045,
715264908,
628829100,
484492064,
919717789,
513196123,
748510389,
403652653,
574455974,
77123823,
172096141,
819801784,
581418893,
15655126,
15391652,
875641535,
203191898,
264582598,
880691101,
907800444,
986598821,
340030191,
264688936,
369832433,
785804644,
842065079,
423951674,
663560047,
696623384,
496709826,
161960209,
331910086,
541120825,
951524114,
841656666,
162683802,
629786193,
190395535,
269571439,
832671304,
76770272,
341080135,
421943723,
494210290,
751040886,
317076664,
672850561,
72482816,
493689107,
135625240,
100228913,
684748812,
639655136,
906233141,
929893103,
277813439,
814362881,
562608724,
406024012,
885537778,
10065330,
60625018,
983737173,
60517502,
551060742,
804930491,
823845496,
727416538,
946421040,
678171399,
842203531,
175638827,
894247956,
538609927,
885362182,
946464959,
116667533,
749816133,
241427979,
871117927,
281804989,
163928347,
563796647,
640266394,
774625892,
59342705,
256473217,
674115061,
918860977,
322633051,
753513874,
393556719,
304644842,
767372800,
161362528,
754787150,
627655552,
677395736,
799289297,
846650652,
816701166,
687265514,
787113234,
358757251,
701220427,
607715125,
245795606,
600624983,
10475577,
728620948,
759404319,
36292292,
491466901,
22556579,
114495791,
647630109,
586445753,
482254337,
718623833,
763514207,
66547751,
953634340,
351472920,
308474522,
494166907,
634359666,
172114298,
865440961,
364380585,
921648059,
965683742,
260466949,
117483873,
962540888,
237120480,
620531822,
193781724,
213092254,
107141741,
602742426,
793307102,
756154604,
236455213,
362928234,
14162538,
753042874,
778983779,
25977209,
49389215,
698308420,
859637374,
49031023,
713258160,
737331920,
923333660,
804861409,
83868974,
682873215,
217298111,
883278906,
176966527,
954913,
105359006,
390019735,
10430738,
706334445,
315103615,
567473423,
708233401,
48160594,
946149627,
346966053,
281329488,
462880311,
31503476,
185438078,
965785236,
992656683,
916291845,
881482632,
899946391,
321900901,
512634493,
303338827,
121000338,
967284733,
492741665,
152233223,
165393390,
680128316,
917041303,
532702135,
741626808,
496442755,
536841269,
131384366,
377329025,
301196854,
859917803,
676511002,
373451745,
847645126,
823495900,
576368335,
73146164,
954958912,
847549272,
241289571,
646654592,
216046746,
205951465,
3258987,
780882948,
822439091,
598245292,
869544707,
698611116,
};
const int Base = 1000000;
LL getFact(LL x) {
if (x < 0)return 0;
LL val = factume[x / Base];
for (LL i = x / Base*Base + 1; i <= x; i++) {
val *= i;
val %= MOD;
}
return val;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
if(0){
cout << "LL fact[] = {\n";
init_fact(1e9 + 1);
FOR(i, 0, 1e9 + 1) {
if (i % Base==0) {
cout << fact[i] <<",\n";
debug(i);
}
}
cout << "};\n";
return 0;
}
int T; cin >> T;
FOR(t, 0, T) {
string sc, sp; cin >> sc >> sp;
PII C = f(sc), P = f(sp);
if (P.second) {
cout << 0 << endl;
continue;
}
if (C.second == 0 && C.first - P.first + 1 < 0) {
cout << 0 << endl;
continue;
}
C.first += MOD - P.first + 1;
C.first %= MOD;
if (C.first- P.first < 0) {
cout << 0 << endl;
continue;
}
LL ans = getFact(C.first);
ans *= modinv(getFact(C.first-P.first));
ans %= MOD;
cout << ans << "\n";
}
return 0;
}