結果
| 問題 | No.148 試験監督（3） |
| ユーザー |
 paruki
|
| 提出日時 | 2016-11-25 16:45:30 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,474 bytes |
| コンパイル時間 | 2,258 ms |
| コンパイル使用メモリ | 174,680 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-27 11:16:15 |
| 合計ジャッジ時間 | 3,773 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 24 ms
5,248 KB |
| testcase_01 | AC | 33 ms
5,248 KB |
| testcase_02 | AC | 83 ms
5,248 KB |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | AC | 4 ms
5,248 KB |
| testcase_10 | AC | 4 ms
5,248 KB |
| testcase_11 | AC | 2 ms
5,248 KB |
ソースコード
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
/***
c < 2p-1の場合
不可
X = 0
c >= 2p-1の場合
X
= p!H(p+1,c-2p+1)
= p!C((p+1)+(c-2p+1)-1, c-2p+1)
= p!C(c-p+1, c-2p+1)
= p!C(c-p+1, c-p+1-(c-2p+1))
= p!C(c-p+1,p)
= p!(c-p+1)!/(p!c-2p+1)!
= (c-p+1)!/(c-2p+1)!
Y = a!/b! mod md (a > b, mdは素数)
floor(a/md) != floor(b/md)の場合
すなわち
a - b >= md の場合
Y
≡a!/b!
≡ a*...*(kmd)*...*b!/b!
≡ a*...*(kmd)*...*(b+1)
≡ a*...*0*...(b+1)
≡ 0
(c-p+1) - (c-2p+1)
= p
より
p>=mdの場合
0
a-b<mdの場合
a' = a mod md
b' = b mod md
とすると
a!/b!
≡(kmd)!*(kmd+1)*(kmd+2)*...*(kmd+a') / (kmd)!*(kmd+1)*(kmd+2)*...*(kmd+b')
≡(kmd+1)*(kmd+2)*...*(kmd+a') / (kmd+1)*(kmd+2)*...*(kmd+b')
≡1*2*...*a' / 1*2*...*b'
≡a'! / b'!
p<mdの
場合も
(c-p+1)!/(c-2p+1)!
が求められた。
***/
int MAGIC[] = {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 MOD = (int)1e9 + 7;
const int R = (int)1e6;
string increment(string s) {
for(int i = (int)s.size() - 1; i >= 0; --i) {
if(s[i] == '9') {
s[i] = '0';
if(i == 0) {
s = '1' + s;
break;
}
} else {
s[i]++;
break;
}
}
return s;
}
string shiftRight(string s) {
string t;
int cur = 0, leading = 1;
for(int i = 0; i < (int)s.size(); ++i) {
cur = s[i] - '0' + cur * 10;
int x = cur >> 1;
if(!leading || x) {
t += (char)(x + '0');
leading = 0;
}
cur &= 1;
}
if(t == "")t = "0";
return t;
}
bool les(string s, string t) {
if(s.size() != t.size())return s.size() < t.size();
return s < t;
}
void generate() {
vector<ll> res(MOD / R + 1);
ll cur = 1;
res[0] = 1;
for(int i = 1; i < MOD; ++i) {
cur = cur * i % MOD;
if(i%R == 0) {
res[i / R] = cur;
}
}
each(r, res) {
cout << r << ',' << endl;
}
}
int digitsToMod(string s) {
long long res = 0;
for(auto c: s) {
res = res * 10 + (c - '0');
if(res >= MOD)res %= MOD;
}
return (int)res;
}
int inverse(int x){
long long a = x, b = MOD, u = 1, v = 0;
while(b) {
long long t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
if(u < 0)u += MOD;
return (int)u;
}
int f(string C, string P) {
string x = increment(C);
x = shiftRight(x);
if(C.back() == '1')x = increment(x);
if(les(x, P) || les(to_string(MOD-1), P)) {
return 0;
}
int c = digitsToMod(C);
int p = digitsToMod(P);
int a = (c - p + 1 + MOD) % MOD;
int b = (c - 2 * p + 1 + MOD) % MOD;
ll A = MAGIC[a / R], B = MAGIC[b / R];
for(int i = (int)a/R*R + 1; i <= a; ++i) A = A*i%MOD;
for(int i = (int)b/R*R + 1; i <= b; ++i) B = B*i%MOD;
int ans = A*inverse((int)B) % MOD;
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T--) {
string C, P;
cin >> C >> P;
cout << f(C, P) << endl;
}
}