HDU6333 Problem B. Harvest of Apples

試験場でこの問題を見たとき、この式は簡略化できない==だったような気がしたので、c(m,0)+c(m,1)+...+c(m,m)c(n,0)+c(n,1)+c(n,2)....+c(n,m)は,前者が2^mであるため,O(1)がmからnに拡大できればよいが,その結果,
c(m,0)+c(m,1)=sum 1(1)式
プッシュ
c(m+1,0)+c(m+1,1)+..c(m+1,m)=sum 2(2)式
の法則
c(m+1,1)-c(m,1)=c(m,0),c(m+1,2)-c(m,2)=c(m,1),
したがって(1)式から(2)に押すとsum 2=sum 1+sum 1-c(m,n)となる.
そしてT=1 e 5,n,m=1 e 5を見ると,突然莫隊を思い浮かべ,n加減1は上の式O(1)で遷移し,m加減1は+c(n,m+1)または-c(n,m)で,lucas+で前処理してもO(1)で遷移できるからである.
6試合余りの学校を打って、私のチームは初めて非署名の問題を出して、私が何度も発揮してモチーム==を思っているような気がします.前回湘潭もモチーム+二分樹状配列Aの主席樹の問題です.の

#include
#define X first
#define Y second
#define pb push_back
#define mk make_pair
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MAXN = 100010;  
const int mod = 1e9 + 7;  

int T,sz;
struct node
{
	int m,n,ind;
}a[maxn];
LL sum;
LL ans[maxn];
LL inv[MAXN + 10], fac[MAXN + 10];

void init()    
{    
    inv[0] = fac[0] = inv[1] = fac[1] = 1;    
    for(int i = 1; i < MAXN; i++)    
    fac[i] = fac[i - 1] * i % mod;    
    for(int i = 2; i < MAXN; i++)    
    inv[i] = (mod - (mod / i)) * inv[mod % i] % mod;//lucas?????    
    for(int i = 1; i < MAXN; i++)    
    inv[i] = inv[i - 1] * inv[i] % mod;     
}  
inline LL C(int n, int m)//???? C n,m     
{    
    if(na[i].n)
		{
			sum=(1ll*((sum+C(r-1,l))%mod)*inv[2])%mod;
			r--;
		}
		while(la[i].m)
{
l--;
sum=(sum-C(r,l+1)+mod)%mod;
}
ans[a[i].ind]=sum;
}
}
inline void print()
{
for(int i=1;i<=T;i++)
printf("%lld",ans[i]);
}
int main()
{
init();
prework();
mainwork();
print();
return 0;
}