QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#30098 | #2811. NoM | myee | 100 ✓ | 26ms | 3312kb | C++11 | 11.6kb | 2022-04-24 19:10:45 | 2022-04-28 12:26:47 |
Judging History
answer
#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
T ans=1%mod;
while(index)
{
if(index&1)ans=ans*base%mod;
base=base*base%mod,index>>=1;
}
return ans;
}
namespace AnyMod
{
ullt Mod=-1;
inline voi ChgMod(ullt v){Mod=v;}
struct ModInt
{
private:
ullt v;inline ullt chg(ullt w){return(w<Mod)?w:w-Mod;}
inline ModInt _chg(ullt w){ModInt ans;ans.v=(w<Mod)?w:w-Mod;return ans;}
public:
ModInt():v(0){}
ModInt(ullt v):v(v%Mod){}
bol empty(){return!v;}
inline ullt val(){return v;}
friend bol operator<(ModInt a,ModInt b){return a.v<b.v;}
friend bol operator>(ModInt a,ModInt b){return a.v>b.v;}
friend bol operator<=(ModInt a,ModInt b){return a.v<=b.v;}
friend bol operator>=(ModInt a,ModInt b){return a.v>=b.v;}
friend bol operator==(ModInt a,ModInt b){return a.v==b.v;}
friend bol operator!=(ModInt a,ModInt b){return a.v!=b.v;}
inline friend ModInt operator+(ModInt a,ModInt b){return a._chg(a.v+b.v);}
inline friend ModInt operator-(ModInt a,ModInt b){return a._chg(a.v+a.chg(Mod-b.v));}
inline friend ModInt operator*(ModInt a,ModInt b){return a.v*b.v;}
friend ModInt operator/(ModInt a,ModInt b){return b._power(Mod-2)*a.v;}
friend ModInt operator^(ModInt a,ullt b){return a._power(b);}
inline ModInt operator-(){return _chg(Mod-v);}
ModInt sqrt()
{
if(power(v,(Mod-1)>>1,Mod)!=1)return 0;
ModInt b=1;do b++;while(b._power((Mod-1)>>1)==1);
ullt t=Mod-1,s=0,k=1;while(!(t&1))s++,t>>=1;
ModInt x=_power((t+1)>>1),e=_power(t);
while(k<s)
{
if(e._power(1llu<<(s-k-1))!=1)x*=b._power((1llu<<(k-1))*t);
e=_power(Mod-2)*x*x,k++;
}
return _min(x,-x),x;
}
ModInt inv(){return _power(Mod-2);}
ModInt _power(ullt index){ModInt ans(1),w(v);while(index){if(index&1)ans*=w;w*=w,index>>=1;}return ans;}
voi read(){v=0;chr c;do c=getchar();while(c>'9'||c<'0');do v=(c-'0'+v*10)%Mod,c=getchar();while(c>='0'&&c<='9');v%=Mod;}
voi print()
{
static chr C[20];uint tp=0;
ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
while(tp--)putchar(C[tp]);
}
voi println(){print(),putchar('\n');}
ModInt operator++(int){ModInt ans=*this;return v=chg(v+1),ans;}
public:
inline ullt&operator()(){return v;}
inline ModInt&operator+=(ModInt b){return*this=_chg(v+b.v);}
inline ModInt&operator-=(ModInt b){return*this=_chg(v+chg(Mod-b.v));}
inline ModInt&operator*=(ModInt b){return*this=v*b.v;}
ModInt&operator^=(ullt b){return*this=_power(b);}
ModInt&operator/=(ModInt b){return*this=b._power(Mod-2)*v;}
ModInt&operator++(){return v=chg(v+1),*this;}
};
}
namespace BF_POLY
{
typedef AnyMod::ModInt modint;
typedef std::vector<modint>modvec;
struct poly
{
std::vector<modint>V;
poly(){}
poly(uint n){V.resize(n);}
poly(std::vector<modint>V):V(V){}
inline modint&operator[](uint n){return V[n];};
inline voi bzr(){V.clear();}
inline voi push(modint v){V.push_back(v);}
inline voi pop(){V.pop_back();}
inline voi cut_zero(){while(!V.empty()&&V.back().empty())V.pop_back();}
inline voi chg_siz(uint n){V.resize(n);}
inline voi chg_deg(uint n){V.resize(n+1);}
inline bol empty(){return cut_zero(),V.empty();}
inline uint size(){return V.size();}
inline uint deg(){return V.size()-1;}
inline modint val(uint n){return(n<size())?V[n]:0;}
inline modvec GET(){return V;}
poly reverse()
{
poly ans;for(uint i=size()-1;~i;i--)ans.push(V[i]);
return ans;
}
friend poly operator+(poly a,poly b)
{
if(a.size()<b.size())a.chg_siz(b.size());
for(uint i=0;i<b.size();i++)a[i]+=b[i];
a.cut_zero();return a;
}
friend poly operator+(poly a,modint v)
{
if(!a.size())a.chg_siz(1);
a[0]+=v;return a;
}
friend poly operator+(modint v,poly a)
{
if(!a.size())a.chg_siz(1);
a[0]+=v;return a;
}
friend poly operator-(poly a){
for(auto&s:a.V)s=-s;
return a;
}
friend poly operator-(poly a,poly b)
{
if(a.size()<b.size())a.chg_siz(b.size());
for(uint i=0;i<b.size();i++)a[i]-=b[i];
a.cut_zero();return a;
}
friend poly operator-(poly a,modint v)
{
if(!a.size())a.chg_siz(1);
a[0]-=v;return a;
}
friend poly operator-(modint v,poly a)
{
if(!a.size())a.chg_siz(1);
a[0]-=v;return-a;
}
friend poly operator*(poly a,poly b)
{
poly ans;ans.chg_siz(a.size()+b.size());
for(uint i=0;i<a.size();i++)for(uint j=0;j<b.size();j++)ans[i+j]+=a[i]*b[j];
ans.cut_zero();
return ans;
}
friend poly operator*(poly A,modint b)
{
for(auto&s:A.V)s*=b;
return A;
}
friend poly operator*(modint b,poly A)
{
for(auto&s:A.V)s*=b;
return A;
}
friend poly operator<<(poly a,uint k)
{
poly ans;ans.chg_siz(k);for(auto v:a.V)ans.push(v);
return ans;
}
friend poly operator>>(poly a,uint k)
{
poly ans;for(uint i=k;i<a.size();i++)ans.push(a[i]);
return ans;
}
friend poly sub_mul(poly a,poly b)
{
uint len=(a=a.reverse()).size();
a=a*b;a.chg_siz(len);a=a.reverse();
return a;
}
poly inv(){return inv(size());}
poly inv(uint prec)
{
if(!prec||!val(0)())return poly();
poly ans(prec);ans[0]=V[0].inv();
for(uint i=1;i<prec;i++)
{
for(uint j=1;j<=i;j++)ans[i]+=ans[i-j]*val(j);
ans[i]*=-ans[0];
}
return ans;
}
poly exp(){return exp(size());}
poly exp(uint prec)
{
if(!prec||val(0)())return poly();
poly ans(prec);
ans[0]=1;
for(uint i=1;i<prec;i++)
{
for(uint j=0;j<i;j++)ans[i]+=val(i-j)*(i-j)*ans[j];
ans[i]/=i;
}
return ans;
}
poly sqrt(){return sqrt(size());}
poly sqrt(uint prec)
{
if(!prec||!val(0)())return poly();
poly ans(prec);
ans[0]=V[0]==1?1:V[0].sqrt();
modint v=ans[0].inv()/2;
for(uint i=1;i<prec;i++)
{
ans[i]=val(i);
for(uint j=1;j<i;j++)ans[i]-=ans[j]*ans[i-j];
ans[i]*=v;
}
return ans;
}
poly&operator+=(poly b)
{
if(size()<b.size())chg_siz(b.size());
for(uint i=0;i<b.size();i++)V[i]+=b[i];
cut_zero();return*this;
}
inline poly&operator+=(modint v)
{
if(!size())chg_siz(1);
V[0]+=v;return*this;
}
poly&operator-=(poly b)
{
if(size()<b.size())chg_siz(b.size());
for(uint i=0;i<b.size();i++)V[i]-=b[i];
cut_zero();return*this;
}
inline poly&operator-=(modint v)
{
if(!size())chg_siz(1);
V[0]-=v;return*this;
}
poly&operator*=(poly b){return*this=*this*b;}
poly&operator*=(modint v)
{
for(auto&t:V)t*=v;
return*this;
}
poly&operator<<=(uint v){return*this=*this<<v;}
poly&operator>>=(uint v){return*this=*this>>v;}
};
struct cpd
{
modint point_eval(poly P,modint x)
{
modint ans;
for(uint i=P.deg();~i;i--)ans=ans*x+P[i];
return ans;
}
poly z_npow(poly P,uint n)
{
if(P.empty())return P;
poly ans(P.deg()*n+1);
for(uint i=0;i<P.size();i++)ans[i*n]+=P[i];
return ans;
}
poly z_npow(poly P,uint n,uint prec)
{
poly ans(prec);
for(uint i=0;i<P.size()&&i*n<prec;i++)ans[i*n]+=P[i];
return ans;
}
poly z_mul_k(poly P,modint k)
{
modint t(1);
for(uint i=0;i<P.size();i++)P[i]*=t,t*=k;
return P;
}
poly z_add_v(poly P,modint v)
{
uint n=P.size();if(!n)return P;
modvec A(n),B(n);
A[0]=1;for(uint i=1;i<n;i++)A[i]=A[i-1]*i;
B[n-1]=A[n-1].inv();for(uint i=n-1;i;i--)B[i-1]=B[i]*i;
poly User(n);modint w(1);
for(uint i=0;i<n;i++)P[i]*=A[i],User[i]=w*B[i],w*=v;
P=sub_mul(P,User),P.chg_siz(n);
for(uint i=0;i<n;i++)P[i]*=B[i];
return P;
}
poly chg_siz(poly P,uint siz){P.chg_siz(siz);return P;}
poly PolyaInv(poly P,uint prec){return(modint(1)-P).inv(prec);}
poly PolyaInv(poly P){return PolyaInv(P,P.size());}
voi println(poly P,uint n)
{
for(uint i=0;i<n;i++){
if(i)putchar(' ');
P.val(i).print();
}
putchar('\n');
}
voi println(poly P){println(P,P.size());}
poly LIM_MUL(poly a,poly b,uint lim)
{
poly ans;ans.chg_siz(lim);
for(uint i=0;i<a.size();i++)for(uint j=0;j<b.size()&&i+j<lim;j++)ans[i+j]+=a[i]*b[j];
ans.cut_zero();
return ans;
}
poly Max_Mul(poly a,poly b)
{
poly ans(std::max(a.size(),b.size()));
modint v=0;for(uint i=0;i<a.size();i++)v+=b.val(i),ans[i]+=v*a[i];
v=0;for(uint i=0;i<b.size();i++)ans[i]+=v*b[i],v+=a.val(i);
return ans;
}
};
};
using namespace BF_POLY;
modint P[4005],Q[4005];
poly Pow(poly P,uint index)
{
poly ans(modvec{1});
while(index)
{
if(index&1)ans*=P;
P*=P,index>>=1;
}
return ans;
}
poly Get(uint n)
{
poly ans(n/2+1);ans[0]=1;
for(uint i=0;i<n/2;i++)ans[i+1]=ans[i]*(n-2*i)*(n-2*i-1);
for(uint i=0;i<=n/2;i++)ans[i]*=Q[i];
return ans;
}
int main()
{
AnyMod::ChgMod(1e9+7);
uint n,m;scanf("%u%u",&n,&m);
uint LIM=n<<1;
P[0]=1;for(uint i=1;i<=LIM;i++)P[i]=P[i-1]*i;
Q[LIM]=P[LIM].inv();for(uint i=LIM;i;i--)Q[i-1]=Q[i]*i;
uint w=n*2/m;uint cnt1=n*2%m;uint cnt0=m-cnt1;
poly X=Pow(Get(w),cnt0)*Pow(Get(w+1),cnt1);
modint ans=0;
for(uint i=0;i<=n;i++)ans+=X.val(i)*((i&1)?-modint(1):1)*P[n]*Q[n-i]*P[n*2-i*2];
ans.println();
return 0;
}
詳細信息
Subtask #1:
score: 9
Accepted
Test #1:
score: 9
Accepted
time: 3ms
memory: 3172kb
input:
1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 3ms
memory: 3220kb
input:
2 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3072kb
input:
2 2
output:
16
result:
ok single line: '16'
Test #4:
score: 0
Accepted
time: 3ms
memory: 3084kb
input:
3 1
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 3ms
memory: 3220kb
input:
3 2
output:
288
result:
ok single line: '288'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3216kb
input:
3 3
output:
384
result:
ok single line: '384'
Test #7:
score: 0
Accepted
time: 3ms
memory: 3172kb
input:
4 2
output:
9216
result:
ok single line: '9216'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3176kb
input:
4 3
output:
13824
result:
ok single line: '13824'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3132kb
input:
5 1
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 3ms
memory: 3100kb
input:
5 5
output:
2088960
result:
ok single line: '2088960'
Subtask #2:
score: 12
Accepted
Dependency #1:
100%
Accepted
Test #11:
score: 12
Accepted
time: 3ms
memory: 3100kb
input:
99 55
output:
117836331
result:
ok single line: '117836331'
Test #12:
score: 0
Accepted
time: 3ms
memory: 3180kb
input:
69 50
output:
427094826
result:
ok single line: '427094826'
Test #13:
score: 0
Accepted
time: 3ms
memory: 3176kb
input:
67 5
output:
733227544
result:
ok single line: '733227544'
Test #14:
score: 0
Accepted
time: 3ms
memory: 3192kb
input:
69 26
output:
730153757
result:
ok single line: '730153757'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3180kb
input:
71 64
output:
100578188
result:
ok single line: '100578188'
Test #16:
score: 0
Accepted
time: 4ms
memory: 3108kb
input:
87 10
output:
410973724
result:
ok single line: '410973724'
Test #17:
score: 0
Accepted
time: 3ms
memory: 3076kb
input:
64 35
output:
623989218
result:
ok single line: '623989218'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3220kb
input:
67 51
output:
312068739
result:
ok single line: '312068739'
Test #19:
score: 0
Accepted
time: 3ms
memory: 3152kb
input:
85 3
output:
796582412
result:
ok single line: '796582412'
Subtask #3:
score: 13
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #20:
score: 13
Accepted
time: 3ms
memory: 3184kb
input:
164 20
output:
152386555
result:
ok single line: '152386555'
Test #21:
score: 0
Accepted
time: 3ms
memory: 3196kb
input:
154 80
output:
741601266
result:
ok single line: '741601266'
Test #22:
score: 0
Accepted
time: 3ms
memory: 3232kb
input:
266 255
output:
245915928
result:
ok single line: '245915928'
Test #23:
score: 0
Accepted
time: 4ms
memory: 3188kb
input:
239 19
output:
511848592
result:
ok single line: '511848592'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3112kb
input:
296 141
output:
462138216
result:
ok single line: '462138216'
Test #25:
score: 0
Accepted
time: 3ms
memory: 3208kb
input:
255 250
output:
727256255
result:
ok single line: '727256255'
Test #26:
score: 0
Accepted
time: 3ms
memory: 3312kb
input:
257 15
output:
253032679
result:
ok single line: '253032679'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3152kb
input:
300 299
output:
559277735
result:
ok single line: '559277735'
Subtask #4:
score: 18
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #28:
score: 18
Accepted
time: 5ms
memory: 3160kb
input:
625 19
output:
787742499
result:
ok single line: '787742499'
Test #29:
score: 0
Accepted
time: 3ms
memory: 3224kb
input:
657 324
output:
660247748
result:
ok single line: '660247748'
Test #30:
score: 0
Accepted
time: 5ms
memory: 3112kb
input:
646 582
output:
830442831
result:
ok single line: '830442831'
Test #31:
score: 0
Accepted
time: 5ms
memory: 3120kb
input:
637 14
output:
468904506
result:
ok single line: '468904506'
Test #32:
score: 0
Accepted
time: 8ms
memory: 3140kb
input:
685 343
output:
516203560
result:
ok single line: '516203560'
Test #33:
score: 0
Accepted
time: 5ms
memory: 3132kb
input:
713 644
output:
225559251
result:
ok single line: '225559251'
Test #34:
score: 0
Accepted
time: 7ms
memory: 3136kb
input:
900 899
output:
941929065
result:
ok single line: '941929065'
Subtask #5:
score: 48
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #35:
score: 48
Accepted
time: 16ms
memory: 3128kb
input:
1624 18
output:
887332511
result:
ok single line: '887332511'
Test #36:
score: 0
Accepted
time: 20ms
memory: 3212kb
input:
1779 1687
output:
611283083
result:
ok single line: '611283083'
Test #37:
score: 0
Accepted
time: 22ms
memory: 3272kb
input:
1603 18
output:
846564825
result:
ok single line: '846564825'
Test #38:
score: 0
Accepted
time: 18ms
memory: 3168kb
input:
1651 818
output:
148850576
result:
ok single line: '148850576'
Test #39:
score: 0
Accepted
time: 19ms
memory: 3264kb
input:
1579 1501
output:
427262684
result:
ok single line: '427262684'
Test #40:
score: 0
Accepted
time: 26ms
memory: 3268kb
input:
2000 1999
output:
510859110
result:
ok single line: '510859110'