結果

問題 No.148 試験監督（3）
ユーザー 沙耶花沙耶花
提出日時 2021-11-02 15:57:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,322 bytes
コンパイル時間 4,983 ms
コンパイル使用メモリ 279,212 KB
実行使用メモリ 5,532 KB
最終ジャッジ日時 2024-10-11 20:21:35
合計ジャッジ時間 8,464 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 AC 114 ms
5,404 KB
testcase_10 AC 113 ms
5,404 KB
testcase_11 AC 106 ms
5,404 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000001

template <class T>
vector<T> convolution_mint(vector<T> a,vector<T> b){
	
	static constexpr unsigned long long M0 = 998244353;
	static constexpr unsigned long long M1 = 754974721;
	static constexpr unsigned long long M2 = 469762049;
	
	vector<long long> aa(a.size()),bb(b.size());
	rep(i,a.size())aa[i] = a[i].val();
	rep(i,b.size())bb[i] = b[i].val();
	
	auto c0 = convolution<M0>(aa,bb);
	auto c1 = convolution<M1>(aa,bb);
	auto c2 = convolution<M2>(aa,bb);
	
	vector<mint> ret(c0.size());
	vector<long long> m = {M0,M1,M2};
	rep(i,c0.size()){		
		
		ret[i] += c0[i];
		
		{
			long long cur = c0[i];
			cur %= M1;
			cur = c1[i]-cur;
			if(cur<0)cur += M1;
			cur *= 416537774;
			cur %= M1;
			
			mint m = M0;
			ret[i] += m*cur;
			
			cur *= M0;
			cur += c0[i];
			cur %= M2;
			cur = c2[i] - cur;
			if(cur<0)cur += M2;
			cur *= 429847628;
			cur %= M2;
			m *= M1;
			ret[i] += m * cur;
		}
	}
	
	return ret;
}

struct fast_factorial{
	vector<mint> block;
	long long sq;
	
	fast_factorial(){
		
		rep(i,100){
			if((1LL<<(i*2))>=mint::mod()){
				sq = i;
				break;
			}
		}
		
		block = {1,1+(1<<sq)};
		
		rep(i,sq){
			
			auto g0 = get(block,1<<i);
			auto g1 = get(block,(1<<i)*(1<<sq));
			auto g2 = get(block,(1<<i)*(1<<sq) + (1<<i));
			
			vector<mint> nb((1<<(i+1))+1);
			
			rep(j,block.size()){
				nb[j] = block[j] * g0[j];
			}
			rep(j,g1.size()){
				nb[i+j] = g1[j] * g2[j];
			}

			swap(block,nb);
		}
		
	}
	
	vector<mint> get(vector<mint> g0,mint a){
		
		mint m = a;
		m /= mint(1<<sq);
		
		vector<mint> ret = get_(g0,a);
		mint p = mint(1<<sq).pow(ret.size()-1);
		rep(i,ret.size())ret[i] *= p;
		
		return ret;
	}
	
	vector<mint> get_(vector<mint> h,mint m){
		
		int d = h.size()-1;
		
		mint fr = 1;
		rep(i,d)fr *= i+1;
		fr = fr.inv();
		
		rep(i,d+1){
			h[i] *= fr;
			h[d-i] *= fr;
			fr *= d-i;
		}
		
		vector<mint> h2(d+1,0);
		rep(i,d+1){
			h2[i] = mint(m + d - i).inv();
		}
		
		vector<mint> ret = convolution_mint(h,h2);
		while(ret.size()!=d+1)ret.pop_back();
		
		fr = 1;
		rep(i,d+1)fr *= m+i;
		
		rep(i,ret.size())ret[i] *= fr;
		
		return ret;
	}
	
	mint query(long long n){
		if(n>=mint::mod())return 0;
		mint ret = block[n>>sq];
		for(int i=((n>>sq)<<sq)+1;i<=n;i++)ret *= i;
		return ret;
	}
};

fast_factorial F;

mint get(int n){
	return F.query(n);
}

void solve(){
	string C,P;
	cin>>C>>P;
	
	if(P.size()>=11){
		cout<<0<<endl;
		return;
	}
	if(P.size()==10 && P>="1000000007"){
		cout<<0<<endl;
		return;
	}
	
	int p = stoi(P);
	if(C.size()<=10){
		long long temp = stoll(C);
		if(temp < (p-1)){
			cout<<0<<endl;
			return;
		}
	}
	mint cur = 0;
	rep(i,C.size()){
		cur *= 10;
		cur += C[i]-'0';
	}
	
	cur -= p;
	cur ++;
	
	if(cur.val() < (cur-p).val()){
		cout<<0<<endl;
		return;
	}
	
	mint ans = get(cur.val());
	ans /= get((cur-p).val());
	
	cout<<ans.val()<<endl;
	
}

int main(){	
//cout<<memo.size()<<endl;
/*
	cout<<"{";
	mint cur = 1;
	mint t = 1;
	rep(i,1001){
		cout<<cur.val();
		if(i!=1000)cout<<',';
		rep(j,1000000){
			cur *= t;
			t++;
		}
	}
	cout<<"}"<<endl;
*/
	int _t;
	cin>>_t;
	
	rep(_,_t)solve();
	
	
	return 0;
	
}
0