#11514 (C++11) No.148 試験監督（3）

提出ソース
結果

問題	No.148 試験監督（3）
ユーザー	anta
提出日時	2015-02-09 00:18:10
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	155 ms / 1,000 ms
コード長	16,782 bytes
コンパイル時間	1,771 ms
コンパイル使用メモリ	87,568 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-05 13:00:44
合計ジャッジ時間	3,269 ms
ジャッジサーバーID （参考情報）	judge15 / judge12
このコードへのチャレンジ（β）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	49 ms 4,380 KB
testcase_01	AC	51 ms 4,376 KB
testcase_02	AC	143 ms 4,380 KB
testcase_03	AC	148 ms 4,376 KB
testcase_04	AC	146 ms 4,380 KB
testcase_05	AC	132 ms 4,380 KB
testcase_06	AC	95 ms 4,380 KB
testcase_07	AC	155 ms 4,376 KB
testcase_08	AC	125 ms 4,380 KB
testcase_09	AC	4 ms 4,376 KB
testcase_10	AC	4 ms 4,376 KB
testcase_11	AC	2 ms 4,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt(): x(0) { }
	ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }
	
	ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
	
	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
	ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
	
	ModInt inverse() const {
		signed a = x, b = MOD, u = 1, v = 0;
		while(b) {
			signed t = a / b;
			a -= t * b; std::swap(a, b);
			u -= t * v; std::swap(u, v);
		}
		if(u < 0) u += Mod;
		ModInt res; res.x = (unsigned)u;
		return res;
	}
};
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
	ModInt<MOD> r = 1;
	while(k) {
		if(k & 1) r *= a;
		a *= a;
		k >>= 1;
	}
	return r;
}
typedef ModInt<1000000007> mint;

int digitsMod(char s[], int n, int m) {
	int x = 0; long long pow10 = 1;
	for(int i = n-1; i >= 0; i --) {
		if((x += pow10 * (s[i] - '0') % m) >= m) x -= m;
		pow10 = pow10 * 10 % m;
	}
	return x;
}

#if 0
#include "C:\Dropbox\backup\implements\Util\TimeIt_Simple.hpp"
template<typename T>
void precomputeUmekomi(T t, unsigned long long maxN, unsigned interval = 1U << 24, ostream &o = cout, int lineMax = 8) {
	const char *umeName = "ume";
	unsigned umeValues = (unsigned)((maxN + interval) / interval);
	o << typeid(T).name() << " " << umeName << "[" << umeValues << "] = {" << endl;
	unsigned i = 0, ii = 0; int linei = 0;
	double startTime = getTime(), prevTime = startTime, cntTime;
	while(1) {
		if(i == 0) {
			fprintf(stderr, "\r%d / %d (%.4f%%); ", ii, umeValues-1, ii * 1. / (umeValues-1));
			cntTime = getTime();
			if(ii != 0) fprintf(stderr, "%.4fs / %.4fs; ", cntTime - prevTime, (cntTime - startTime) / ii);
			prevTime = cntTime;
			fflush(stderr);
			if(linei == 0) {
				if(ii != 0) {
					o << endl;
				}
				linei = lineMax;
			}
			o << t << ",";
			linei --;
			if(++ ii == umeValues) break;
			i = interval;
		}
		t.step();
		i --;
	}
	o << endl;
	o << "};" << endl;
}
#endif

template<typename T, int VALUES>
T computeWithUmekomi(const T (&ume)[VALUES], unsigned long long N, unsigned interval = 1U << 24) {
	unsigned long long idx = N / interval;
	if(idx >= VALUES) {
		cerr << "computeWithUmekomi: N >= " << interval * VALUES << endl;
		idx = VALUES - 1;
	}
	T t = ume[idx];
	unsigned i = (unsigned)(N - idx * interval);
	while(i > 0) {
		t.step();
		i --;
	}
	return t;
}

struct FactorialMotInt {
	int i; mint cnt;
	static FactorialMotInt init() {
		FactorialMotInt t = { 0, 1 };
		return t;
	}
	inline void step() {
		cnt *= ++ i;
	}
	friend ostream &operator<<(ostream &o, const FactorialMotInt &t) {
		return o << "{" << t.i << "," <<  t.cnt.get() << "}";
	}
	mint get() const { return cnt; }
};

struct FactorialMotInt ume[501] = {
{0,1},{2000000,578095319},{4000000,259081142},{6000000,316220877},{8000000,251368199},{10000000,682498929},{12000000,95936601},{14000000,167332441},
{16000000,336060741},{18000000,626497524},{20000000,491101308},{22000000,565768255},{24000000,968999},{26000000,638587686},{28000000,19426633},{30000000,76479948},
{32000000,842267748},{34000000,485348706},{36000000,544075857},{38000000,798967520},{40000000,723816384},{42000000,721996174},{44000000,323604647},{46000000,398699886},
{48000000,294587621},{50000000,67347853},{52000000,196447201},{54000000,228338256},{56000000,762479457},{58000000,811667359},{60000000,27368307},{62000000,59469516},
{64000000,766196482},{66000000,86609485},{68000000,340941507},{70000000,625544428},{72000000,808412394},{74000000,585237443},{76000000,361786913},{78000000,595143852},
{80000000,199888908},{82000000,579691190},{84000000,459188207},{86000000,439729802},{88000000,899297830},{90000000,888050723},{92000000,736550105},{94000000,85990869},
{96000000,56305184},{98000000,168891766},{100000000,927880474},{102000000,934814019},{104000000,567277637},{106000000,44930135},{108000000,47401357},{110000000,281863274},
{112000000,692636218},{114000000,14235602},{116000000,400295761},{118000000,421835306},{120000000,661224977},{122000000,168203998},{124000000,544064410},{126000000,583967898},
{128000000,751231582},{130000000,623534362},{132000000,243276029},{134000000,60050552},{136000000,395891998},{138000000,159554990},{140000000,970055531},{142000000,487998999},
{144000000,82104855},{146000000,513365505},{148000000,1559745},{150000000,261384175},{152000000,323214113},{154000000,444090941},{156000000,80729842},{158000000,664989237},
{160000000,195888993},{162000000,457882808},{164000000,212938473},{166000000,827544702},{168000000,677711203},{170000000,66404266},{172000000,195290384},{174000000,349551356},
{176000000,83489485},{178000000,52167191},{180000000,547665832},{182000000,350016754},{184000000,296269301},{186000000,23015220},{188000000,748566338},{190000000,109838563},
{192000000,105574531},{194000000,542432219},{196000000,325636655},{198000000,630621321},{200000000,933245637},{202000000,238971581},{204000000,557301633},{206000000,848952161},
{208000000,925152039},{210000000,724691727},{212000000,238087006},{214000000,910291942},{216000000,492237273},{218000000,834860913},{220000000,368925948},{222000000,740594930},
{224000000,806047532},{226000000,172115341},{228000000,116261993},{230000000,268838846},{232000000,243624360},{234000000,481661251},{236000000,95182730},{238000000,115435332},
{240000000,136026497},{242000000,710729672},{244000000,366384665},{246000000,270239666},{248000000,79874094},{250000000,112390913},{252000000,103056890},{254000000,339464594},
{256000000,108312174},{258000000,479334442},{260000000,135498044},{262000000,591048681},{264000000,353339603},{266000000,839849206},{268000000,736265527},{270000000,217544623},
{272000000,618898635},{274000000,380858207},{276000000,898554793},{278000000,54062950},{280000000,419363534},{282000000,160398980},{284000000,990918946},{286000000,450718279},
{288000000,648991369},{290000000,500780548},{292000000,39052406},{294000000,460373282},{296000000,461415770},{298000000,643638805},{300000000,668123525},{302000000,673464765},
{304000000,199866123},{306000000,841799766},{308000000,504962686},{310000000,128487469},{312000000,299172297},{314000000,577786541},{316000000,773206631},{318000000,204355779},
{320000000,30977140},{322000000,363172638},{324000000,472935553},{326000000,587220627},{328000000,793270300},{330000000,522049725},{332000000,335416359},{334000000,472012302},
{336000000,332139472},{338000000,464599136},{340000000,309058615},{342000000,580204973},{344000000,954840109},{346000000,895609896},{348000000,836813268},{350000000,386027524},
{352000000,724205533},{354000000,715247054},{356000000,830567832},{358000000,68409439},{360000000,189239124},{362000000,943653305},{364000000,811056092},{366000000,825132993},
{368000000,985084650},{370000000,148528617},{372000000,882148737},{374000000,701445829},{376000000,302177126},{378000000,241107368},{380000000,940567523},{382000000,325334066},
{384000000,115312728},{386000000,218129285},{388000000,180002392},{390000000,917084264},{392000000,435327356},{394000000,421623838},{396000000,59883031},{398000000,79716267},
{400000000,429277690},{402000000,316486674},{404000000,940338439},{406000000,940524812},{408000000,833550543},{410000000,996164327},{412000000,697611981},{414000000,274192146},
{416000000,925347821},{418000000,893732627},{420000000,358655417},{422000000,581830879},{424000000,347046911},{426000000,125354499},{428000000,247662371},{430000000,568392357},
{432000000,209244402},{434000000,149586983},{436000000,309134554},{438000000,263053337},{440000000,780072518},{442000000,990826116},{444000000,155569943},{446000000,711553356},
{448000000,451373308},{450000000,462639908},{452000000,654611901},{454000000,41815820},{456000000,675258797},{458000000,934281721},{460000000,275105629},{462000000,325912072},
{464000000,252551589},{466000000,554917439},{468000000,754363835},{470000000,909210595},{472000000,719566487},{474000000,424989675},{476000000,50590510},{478000000,198768464},
{480000000,99199382},{482000000,747407118},{484000000,497196934},{486000000,726997875},{488000000,296229203},{490000000,703397904},{492000000,732868367},{494000000,26031303},
{496000000,216665960},{498000000,352946234},{500000000,733333339},{502000000,459878625},{504000000,16634739},{506000000,68718097},{508000000,404206040},{510000000,97830135},
{512000000,31131935},{514000000,864326453},{516000000,167831173},{518000000,718498895},{520000000,608823837},{522000000,385388084},{524000000,681756977},{526000000,313132653},
{528000000,442795120},{530000000,256141983},{532000000,636578562},{534000000,553033642},{536000000,919273670},{538000000,326686486},{540000000,141827977},{542000000,693305776},
{544000000,186576440},{546000000,565456578},{548000000,519397500},{550000000,696628828},{552000000,370732451},{554000000,915265013},{556000000,923043932},{558000000,777901604},
{560000000,637939935},{562000000,490676632},{564000000,462528877},{566000000,798895521},{568000000,699767918},{570000000,811575797},{572000000,606870929},{574000000,179111720},
{576000000,508038818},{578000000,752550134},{580000000,848924691},{582000000,34629406},{584000000,435904287},{586000000,208184231},{588000000,206330671},{590000000,131772368},
{592000000,648711554},{594000000,523696723},{596000000,25058942},{598000000,817928963},{600000000,724464507},{602000000,701453022},{604000000,281230685},{606000000,596949867},
{608000000,303076380},{610000000,272814771},{612000000,48824684},{614000000,939889684},{616000000,48527183},{618000000,484458461},{620000000,326159309},{622000000,668422905},
{624000000,965656187},{626000000,359960756},{628000000,407934361},{630000000,456152084},{632000000,124804049},{634000000,920251227},{636000000,483924582},{638000000,167087470},
{640000000,903466878},{642000000,368114731},{644000000,388728584},{646000000,249153339},{648000000,322908524},{650000000,92255682},{652000000,15570863},{654000000,744158074},
{656000000,334326205},{658000000,98349682},{660000000,769795511},{662000000,888146074},{664000000,582627184},{666000000,919419361},{668000000,986708498},{670000000,373745190},
{672000000,256853930},{674000000,702823274},{676000000,308186532},{678000000,180350107},{680000000,606241871},{682000000,273712630},{684000000,682189174},{686000000,946867127},
{688000000,502371023},{690000000,825871994},{692000000,701506133},{694000000,341779962},{696000000,815463367},{698000000,49187570},{700000000,957939114},{702000000,933376898},
{704000000,338121343},{706000000,869630152},{708000000,632627667},{710000000,435887178},{712000000,129621197},{714000000,827722926},{716000000,918513230},{718000000,547838438},
{720000000,852304035},{722000000,689189630},{724000000,567033437},{726000000,212842957},{728000000,404149413},{730000000,663307737},{732000000,206282795},{734000000,488906585},
{736000000,280700600},{738000000,534279149},{740000000,375297772},{742000000,922377372},{744000000,219932130},{746000000,701050258},{748000000,863002719},{750000000,217598709},
{752000000,810551911},{754000000,247844667},{756000000,812283640},{758000000,857241854},{760000000,624148346},{762000000,564827277},{764000000,478982047},{766000000,454039189},
{768000000,48562889},{770000000,671734977},{772000000,508831870},{774000000,897162044},{776000000,892168027},{778000000,277714559},{780000000,624500515},{782000000,808691930},
{784000000,895205045},{786000000,628829100},{788000000,919717789},{790000000,748510389},{792000000,574455974},{794000000,172096141},{796000000,581418893},{798000000,15391652},
{800000000,203191898},{802000000,880691101},{804000000,986598821},{806000000,264688936},{808000000,785804644},{810000000,423951674},{812000000,696623384},{814000000,161960209},
{816000000,541120825},{818000000,841656666},{820000000,629786193},{822000000,269571439},{824000000,76770272},{826000000,421943723},{828000000,751040886},{830000000,672850561},
{832000000,493689107},{834000000,100228913},{836000000,639655136},{838000000,929893103},{840000000,814362881},{842000000,406024012},{844000000,10065330},{846000000,983737173},
{848000000,551060742},{850000000,823845496},{852000000,946421040},{854000000,842203531},{856000000,894247956},{858000000,885362182},{860000000,116667533},{862000000,241427979},
{864000000,281804989},{866000000,563796647},{868000000,774625892},{870000000,256473217},{872000000,918860977},{874000000,753513874},{876000000,304644842},{878000000,161362528},
{880000000,627655552},{882000000,799289297},{884000000,816701166},{886000000,787113234},{888000000,701220427},{890000000,245795606},{892000000,10475577},{894000000,759404319},
{896000000,491466901},{898000000,114495791},{900000000,586445753},{902000000,718623833},{904000000,66547751},{906000000,351472920},{908000000,494166907},{910000000,172114298},
{912000000,364380585},{914000000,965683742},{916000000,117483873},{918000000,237120480},{920000000,193781724},{922000000,107141741},{924000000,793307102},{926000000,236455213},
{928000000,14162538},{930000000,778983779},{932000000,49389215},{934000000,859637374},{936000000,713258160},{938000000,923333660},{940000000,83868974},{942000000,217298111},
{944000000,176966527},{946000000,105359006},{948000000,10430738},{950000000,315103615},{952000000,708233401},{954000000,946149627},{956000000,281329488},{958000000,31503476},
{960000000,965785236},{962000000,916291845},{964000000,899946391},{966000000,512634493},{968000000,121000338},{970000000,492741665},{972000000,165393390},{974000000,917041303},
{976000000,741626808},{978000000,536841269},{980000000,377329025},{982000000,859917803},{984000000,373451745},{986000000,823495900},{988000000,73146164},{990000000,847549272},
{992000000,646654592},{994000000,205951465},{996000000,780882948},{998000000,598245292},{1000000000,698611116},
};


const int Interval = 2000000;
mint factorial(int n) {
	return computeWithUmekomi(ume, n, Interval).get();
}

int main() {
//	precomputeUmekomi<FactorialMotInt>(FactorialMotInt::init(), mint::Mod, Interval);
	//f(n,p) = f(n-1,p) + f(n-2,p-1)
	//A011973
	//= C(n+1-p,p) * p!
	//= (n-p+1)! / (n-2p+1)!
	//= product [n-2p+2..n-p+1]
	//p<Modと仮定すると、Mod取ってやっても周回することがない。
	//埋め込み…(ヒントはコードサイズ、か)

	int T;
	scanf("%d", &T);
	char *C = new char[10002], *P = new char[10002];
	rep(ii, T) {
		scanf("%s%s", C, P);
		mint ans;
		long long pp;
		if(strlen(P) >= 11) {
			pp = INFL;
		}else {
			sscanf(P, "%lld", &pp);
		}
		long long nn;
		if(strlen(C) <= 10) {
			sscanf(C, "%lld", &nn);
		}else {
			nn = INFL;
		}
		if(pp >= mint::Mod) {
			ans = 0;
		}else if(nn < pp * 2 - 1) {
			ans = 0;
		}else if(pp == 0) {
			ans = 1;
		}else if(nn == 0) {
			ans = 0;
		}else {
			mint n = digitsMod(C, strlen(C), mint::Mod);
			mint p = digitsMod(P, strlen(P), mint::Mod);

			int L = (n - p * 2 + 2).get(), R = (n - p + 1).get();
			if(L > R || L == 0) {
				//0を含む
				ans = 0;
			}else {
				//product[L..R] = R! / (L-1)!
				ans = factorial(R);
				ans /= factorial(L-1);
			}
		}
		printf("%d\n", ans.get());
	}
	return 0;
}
yukicoder

結果

テストケース

ソースコード
