企业官网建设流程全解析

P11767 「KFCOI Round #1」缥缈

题目背景

这个世界这么大，是机缘让我们相遇，也是机缘促使我们分开。

是爱情促使我们沉沦，也是爱情让我们形同陌路。

在这一路上，为什么就刚好喜欢上你呢？

题目描述

你需要求出满足如下条件的长度为mmm的序列BBB的个数：

• BBB中全为正整数。
• BBB中不包含xxx。
• BBB中元素两两不同。
• BBB中元素在范围[1,n][1,n][1,n]中。
• BBB中任意两个元素相差不会超过ttt。

qqq次询问，每次给出xxx和ttt。

由于结果可能很大，输出答案对109+710^9+7109+7取余的结果。

输入格式

本题输入均为正整数。

第一行三个数n,m,qn,m,qn,m,q。

接下来qqq行，每行两个数x,tx,tx,t代表一个询问。

输出格式

输出qqq行，每行一个数，第iii行代表第iii次询问的答案对109+710^9+7109+7取余的结果。

输入输出样例 #1

输入 #1

6 3 3 1 3 2 3 3 5

输出 #1

42 30 60

输入输出样例 #2

输入 #2

10 7 5 3 9 8 6 5 7 9 6 10 7

输出 #2

181440 5040 15120 10080 75600

说明/提示

数据范围

本题采用捆绑测试。

• Subtask 1（10 points）：n≤12n \le 12n≤12，m≤7m\le 7m≤7，q≤10q\le 10q≤10。
• Subtask 2（15 points）：n≤2000n \le 2000n≤2000，m=2m=2m=2，q≤2000q\le 2000q≤2000。
• Subtask 3（15 points）：m=2m=2m=2。
• Subtask 4（20 points）：x≤tx\le tx≤t。
• Subtask 5（40 points）：无特殊限制。

对于所有测试数据，2≤n≤2×1052\le n \le 2 \times 10 ^52≤n≤2×105，2≤m≤n2 \le m \le n2≤m≤n，1≤x≤n1 \le x \le n1≤x≤n，m−1≤t<nm - 1\le t < nm−1≤t<n，1≤q≤2×1051 \le q \le 2\times 10^51≤q≤2×105。

C++实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constll mod=1e9+7;constll M=2e5+10;ll fac[M],inv[M];llqpow(ll a,ll b){ll res=1;while(b){if(b&1ll)res=res*a%mod;a=a*a%mod;b>>=1;}returnres%mod;}llC(ll n,ll m){returnfac[n]%mod*inv[m]%mod*inv[n-m]%mod;}intmain(){fac[0]=1;inv[0]=1;for(ll i=1;i<=200000;i++){fac[i]=fac[i-1]*i%mod;inv[i]=qpow(fac[i],mod-2);}ll n,m,q;cin>>n>>m>>q;while(q--){ll x,t,ans=0;cin>>x>>t;ll all=n-t,have_x_cnt=0;have_x_cnt=(min(n,x+t)-t)-(max(1ll,x-t))+1;ans+=have_x_cnt%mod*C(t,m)%mod;ans%=mod;ans+=(all-have_x_cnt)%mod*C(t+1,m)%mod;ans%=mod;all=(n-t)-2+1,have_x_cnt=0;have_x_cnt=(min(n-1,x+t-1)-(t-1))-max(2ll,x-(t-1))+1;if(t-1>=m)ans=(ans+mod-have_x_cnt*C(t-1,m))%mod;ans=(ans+mod)%mod;ans=(ans+mod-(all-have_x_cnt)*C(t,m))%mod;ans=(ans+mod)%mod;ans=ans%mod*fac[m]%mod;cout<<ans<<"\n";}return0;}