BZOJ 4402:Clarisの剣

その本質によって,この方法の構造が繰り返されず,よくなるように構造方法を作ることができる.
最大の数をTとすると(n-T)の余分が必要になるので(n-T)>>1に相当してT個の箱に入れて空き箱に注意してもいいです
では、C(⌊t 2⌋+T,T)に貢献します.ここには、階乗逆元を求める小さなテクニックがあります.まずNを求めます.の逆元では(N−1)!の逆元でいいO(1)計算

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const
   int Mod=1000000007;
int fact[2000001],fact_[20000001];
inline int Cal(int x,int y)
{
   if(x<0)return 0;
   x>>=1;
   if(x==0)return 1;
   return fact[x+y]*1ll*fact_[x]%Mod*fact_[y]%Mod;
}
int Max=2000000;

int f(int x,int y)
{
   if(y==1)return x;
   int t=f(x,y>>1);
   if(y&1)return t*1ll*t%Mod*1ll*x%Mod;
   else return t*1ll*t%Mod;
}

int ff(int x,int y)
{
    int base=1,res=1,M=x;
    while(y)
    {
       if(y&base)
           y^=base,res=res*1ll*M%Mod;
        base<<=1;
        M=M*1ll*M%Mod;
    }
return res;
}

char c;
inline void read(int &a)
{
  a=0;do c=getchar();while(c<'0'||c>'9');
  while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();
}

int main()
{
    int i,j,k;
    int n,m;
    read(n),read(m); 
    fact[1]=1;
    Max=min(Max,max(n,m)+4);
    for(i=2;i<=Max;i++)
    fact[i]=fact[i-1]*1ll*i%Mod;
   fact_[Max]=ff(fact[Max],Mod-2);
    for(int i=Max-1;i;i--)
     fact_[i]=fact_[i+1]*(i+1ll)%Mod;
    int ans=0;
     if(n&&m)ans=1; 
  for(i=2;i<=m;i++){(ans+=Cal(n-i,i-1))%=Mod;(ans+=Cal(n-i-1,i-1))%=Mod; } 
  printf("%d
",ans);
    return 0;
}