A
使用差分来维护,最后特判即可
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 返回m天后高度为奇数的树的数量 * @param n int整型 * @param m int整型 * @param l int整型vector * @param r int整型vector * @return int整型 */ int sum[200050]; int oddnumber(int n, int m, vector<int>& l, vector<int>& r) { // write code here memset(sum,0,sizeof(sum)); for(int i=0;i<l.size();i++){ sum[l[i]]++; sum[r[i]+1]--; } sum[0]=m; for(int i=0;i<=n;i++){ sum[i]+=sum[i-1]; } int x = 0; for(int i=1;i<=n;i++){ if(sum[i]&1)x++; } return x; } };
B
生成函数的题目,根据题意得到下面五个函数
进行麦克劳林展开得到n的系数为
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @return long长整型 */ long long wwork(int n) { // write code here return 1ll*(n+1)*(n+2)/2; } };
C
总共有个选择方案,假设有m个数必a[i]小,那么概率为
#define ll long long const int mod = 1e9+7; class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @param k int整型 * @param Point int整型vector * @return int整型vector */ static const int N = 2E5+10; int fac[N],Inv[N]; ll quick_pow(ll x,int y){ ll res = 1; while(y){ if(y&1)res=res*x%mod; x=x*x%mod; y>>=1; } return res; } void init(){ memset(fac,0,sizeof(fac)); memset(Inv,0,sizeof(Inv)); fac[0]=1; for(int i=1;i<N;i++){ fac[i]=1ll*i*fac[i-1]%mod; } Inv[N-1]=quick_pow(fac[N-1],mod-2); for(int i=N-2;i>=0;i--)Inv[i]=1ll*Inv[i+1]*(i+1)%mod; } ll C(int n,int m){ if(m>n)return 0; return 1ll*fac[n]*Inv[n-m]%mod*Inv[m]%mod; } vector<pair<int,int>>vp; vector<int> city(int n, int k, vector<int>& Point) { // write code here init(); for(int i=0;i<Point.size();i++){ vp.push_back({Point[i],i}); } sort(vp.begin(),vp.end()); vector<int>ans(Point.size(),Point.size()); ll fm = quick_pow(C(n,k),mod-2); for(int i=0;i<vp.size();i++){ auto s = vp[i]; ll fz = C(i,k-1); ans[s.second] = fz*fm%mod; } return ans; } };