結果
| 問題 | No.148 試験監督（3） |
| コンテスト | |
| ユーザー |
 vjudge1
|
| 提出日時 | 2026-10-16 20:33:27 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
RE
不安定
|
| 実行時間 | - |
| コード長 | 6,377 bytes |
| 記録 | |
| コンパイル時間 | 3,638 ms |
| コンパイル使用メモリ | 381,888 KB |
| 実行使用メモリ | 17,296 KB |
| 最終ジャッジ日時 | 2026-10-16 20:33:40 |
| 合計ジャッジ時間 | 7,896 ms |
|
ジャッジサーバーID （参考情報） |
judge5_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 RE * 9 |
ソースコード
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
const int MOD=1000000007;
typedef complex<double> cd;
const double PI=acos(-1.0);
long long modpow(long long a,long long e){long long r=1;for(;e;e>>=1,a=a*a%MOD)if(e&1)r=r*a%MOD;return r;}
long long modinv(long long a){return modpow(a,MOD-2);}
void fft(vector<cd>&a,bool inv){
int n=a.size();
for(int i=1,j=0;i<n;i++){
int b=n>>1;for(;j&b;b>>=1)j^=b;j^=b;
if(i<j)swap(a[i],a[j]);
}
for(int len=2;len<=n;len<<=1){
double ang=2*PI/len*(inv?-1:1);cd wlen(cos(ang),sin(ang));
for(int i=0;i<n;i+=len){cd w(1);for(int j=0;j<len/2;j++){
cd u=a[i+j],v=a[i+j+len/2]*w;a[i+j]=u+v;a[i+j+len/2]=u-v;w*=wlen;}}
}
if(inv)for(auto&x:a)x/=n;
}
vector<long long> pmul(const vector<long long>&A,const vector<long long>&B){
if(A.empty()||B.empty())return{};
int sa=A.size(),sb=B.size();
if((long long)sa*sb<=400){
vector<long long>r(sa+sb-1);
for(int i=0;i<sa;i++)for(int j=0;j<sb;j++)r[i+j]=(r[i+j]+A[i]*B[j])%MOD;
return r;
}
int n=1;while(n<sa+sb-1)n<<=1;
const long long B_=1LL<<15;
vector<cd>fa(n),fb(n);
for(int i=0;i<sa;i++)fa[i]=cd(A[i]&32767,A[i]>>15);
for(int i=0;i<sb;i++)fb[i]=cd(B[i]&32767,B[i]>>15);
fft(fa,false);fft(fb,false);
vector<cd>c0(n),c1(n),c2(n);
for(int i=0;i<n;i++){
cd ca=conj(fa[(n-i)&(n-1)]),cb=conj(fb[(n-i)&(n-1)]);
cd a0=(fa[i]+ca)*0.5,a1=(fa[i]-ca)*cd(0,-0.5);
cd b0=(fb[i]+cb)*0.5,b1=(fb[i]-cb)*cd(0,-0.5);
c0[i]=a0*b0;c1[i]=a1*b1;c2[i]=(a0+a1)*(b0+b1)-c0[i]-c1[i];
}
fft(c0,true);fft(c1,true);fft(c2,true);
vector<long long>r(sa+sb-1);
for(int i=0;i<(int)r.size();i++){
long long v0=(long long)llround(c0[i].real());
long long v1=(long long)llround(c2[i].real());
long long v2=(long long)llround(c1[i].real());
long long v=((v0%MOD)+MOD)%MOD;
v=(v+v1%MOD*B_)%MOD;
v=(v+v2%MOD*((B_*B_)%MOD))%MOD;
r[i]=(v+MOD)%MOD;
}
return r;
}
void trim(vector<long long>&a){while(a.size()>1&&a.back()==0)a.pop_back();}
vector<long long> pinv(const vector<long long>&a,int n){
vector<long long>r(1,modinv(a[0]));int cur=1;
while(cur<n){
cur<<=1;
vector<long long>t(a.begin(),a.begin()+min((int)a.size(),cur));t.resize(cur);
auto rr=pmul(r,r);rr.resize(cur);
rr=pmul(rr,t);rr.resize(cur);
r.resize(cur);
for(int i=0;i<cur;i++)r[i]=(2LL*r[i]%MOD-rr[i]+MOD)%MOD;
}
r.resize(n);return r;
}
vector<long long> prem(vector<long long>a,const vector<long long>&b){
trim(a);int n=(int)a.size()-1,m=(int)b.size()-1;
if(n<m){trim(a);return a;}
int k=n-m+1;
vector<long long>ar(a.rbegin(),a.rend());ar.resize(k);
vector<long long>br(b.rbegin(),b.rend());br.resize(k);
auto bi=pinv(br,k);
auto qr=pmul(ar,bi);qr.resize(k);
reverse(qr.begin(),qr.end());
auto qb=pmul(qr,b);
vector<long long>r=a;
if((int)r.size()<(int)qb.size())r.resize(qb.size());
for(int i=0;i<(int)qb.size();i++){r[i]-=qb[i];if(r[i]<0)r[i]+=MOD;}
if((int)r.size()>m)r.resize(m);
trim(r);return r;
}
vector<long long> mpe(const vector<long long>&F,const vector<long long>&pt){
int n=pt.size();if(!n)return{};
int sz=1;while(sz<n)sz<<=1;
vector<vector<long long>>tr(2*sz);
for(int i=0;i<n;i++){long long v=(MOD-pt[i]%MOD)%MOD;tr[sz+i]={v,1};}
for(int i=sz-1;i>=1;i--){tr[i]=pmul(tr[i<<1],tr[i<<1|1]);trim(tr[i]);}
vector<vector<long long>>res(2*sz);
res[1]=prem(F,tr[1]);
for(int i=1;i<sz;i++){
if(!res[i].empty()){
res[i<<1]=prem(res[i],tr[i<<1]);
res[i<<1|1]=prem(res[i],tr[i<<1|1]);
}
}
vector<long long>ans(n);
for(int i=0;i<n;i++)ans[i]=res[sz+i].empty()?0:res[sz+i][0];
return ans;
}
long long fall(long long n,long long k){
if(k==0)return 1;if(n<k)return 0;
if(k<=20000000){long long r=1;for(long long i=0;i<k;i++)r=r*(n-i)%MOD;return r;}
long long m=(long long)sqrt((double)k);if(m<1)m=1;
long long q=k/m,rem=k-q*m;
int sz=1;while(sz<(int)q)sz<<=1;
vector<vector<long long>>tr(2*sz);
for(int i=0;i<(int)q;i++){long long v=(n-i*m)%MOD;if(v<0)v+=MOD;tr[sz+i]={v,1};}
for(int i=sz-1;i>=1;i--){tr[i]=pmul(tr[i<<1],tr[i<<1|1]);trim(tr[i]);}
vector<long long>G=tr[1];
vector<long long>pts(q);for(long long i=0;i<q;i++){long long v=(n-i*m)%MOD;if(v<0)v+=MOD;pts[i]=v;}
auto vals=mpe(G,pts);
long long r=1;for(long long v:vals)r=r*v%MOD;
for(long long j=q*m;j<k;j++)r=r*((n-j)%MOD+MOD)%MOD;
return r;
}
string strip0(string s){int i=0;while(i+1<(int)s.size()&&s[i]=='0')i++;return s.substr(i);}
int scmp(string a,string b){
a=strip0(a);b=strip0(b);
if(a.size()!=b.size())return a.size()<b.size()?-1:1;
if(a<b)return -1;if(a>b)return 1;return 0;
}
string sadd(string a,long long v){
int i=(int)a.size()-1;
while(v&&i>=0){int d=a[i]-'0'+(v%10);v/=10;a[i]='0'+(d%10);if(d>=10)v++;i--;}
while(v){a.insert(a.begin(),'0'+(char)(v%10));v/=10;}
return strip0(a);
}
string ssub(string a,long long v){
int i=(int)a.size()-1;
while(v&&i>=0){int d=a[i]-'0'-(v%10);v/=10;if(d<0){d+=10;v++;}a[i]='0'+d;i--;}
return strip0(a);
}
pair<string,long long> sdivmod(string s,long long m){
long long r=0;string q;
for(char c:s){r=r*10+(c-'0');q.push_back((char)('0'+r/m));r%=m;}
return {strip0(q),r};
}
long long stoll_mod(string s,bool&big){
s=strip0(s);long long v=0;big=false;
for(char c:s){v=v*10+(c-'0');if(v>=MOD){big=true;break;}}
return v;
}
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;cin>>T;
while(T--){
string Cs,Ps;cin>>Cs>>Ps;
Cs=strip0(Cs);Ps=strip0(Ps);
if(Ps=="0"){cout<<1<<"\n";continue;}
bool big;long long P=stoll_mod(Ps,big);
if(big){cout<<0<<"\n";continue;}
if(P==0){cout<<1<<"\n";continue;}
if(scmp(Cs,ssub(sadd(Ps,P),1))<0){cout<<0<<"\n";continue;}
string ns=ssub(sadd(Cs,1),P);
string nps=ssub(ns,P);
auto[q1,r1]=sdivmod(ns,MOD);
auto[q2,r2]=sdivmod(nps,MOD);
if(strip0(q1)!=strip0(q2)){cout<<0<<"\n";continue;}
long long n=((r1%MOD)+MOD)%MOD;
if(n<P){cout<<0<<"\n";continue;}
cout<<fall(n,P)<<"\n";
}
}