首页 > 其他分享 >#排列组合#CF1550D Excellent Arrays

#排列组合#CF1550D Excellent Arrays

时间:2024-02-07 09:00:27浏览次数:27  
标签:Arrays mn mid int CF1550D ans Excellent mx mod

洛谷传送门
CF1550D


分析

对于excellent的 \(a\) 来说 \(|a_i-i|=x\) 的值是固定的,考虑枚举它

一半正一半负时函数值是最大的,当 \(n\) 为奇数时要分为两种情况(不过可以通过杨辉三角合并)

问题是,由于 \(l,r\) 的范围,并不能做到所有位置都能可正可负,不过不超过 \(mn=\min\{1-l,r-n\}\) 时是可以的,也就是 \(C(n,mid)*mn\)。

之后应分为两个阶段,绝对值增加1会产生1个不能可正可负,不超过 \(mx=\max\{1-l,r-n\}\) 时,枚举 \(i(mn+i=x)\) 即为 \(C(n-i,mid-i)\)

或者产生2个不能可正可负,此时在上一阶段的上界基础上继续增加,就是 \(C(n-i*2-(mx-mn),mid-i-(mx-mn))\)

注意 \(i\) 在第一阶段超过 \(mid\) 抑或是第二阶段超过 \(mid-(mx-mn)\) 时已经无法产生贡献,此时可直接终止,那么复杂度就是 \(O(n)\) 的


代码(里面的 \(mx\) 已经减去了 \(mn\))

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int N=200011,mod=1000000007;
int inv[N],fac[N],n,L,R,mn,mx,mid,odd,ans;
int iut(){
    int ans=0,f=1; char c=getchar();
    while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
    while (isdigit(c)) ans=ans*10+c-48,c=getchar();
    return ans*f;
}
void print(int ans){
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}
void Mo(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
int C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main(){
    fac[0]=inv[0]=fac[1]=inv[1]=1;
    for (int i=2;i<N;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for (int i=2;i<N;++i) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*inv[i-1]*inv[i]%mod;
    for (int T=iut();T;--T,putchar(10)){
        n=iut(),L=iut(),R=iut(),mid=(n+1)>>1;
        mn=min(1-L,R-n),mx=max(1-L,R-n)-mn;
        odd=n&1,ans=1ll*mn*C(n+odd,mid)%mod;
        for (int i=1;i<=mx&&i<=mid;++i) Mo(ans,C(n-i+odd,mid-i));
        for (int i=1;i<=mid-mx&&i*2+mx<=n;++i) Mo(ans,C(n-i*2-mx+odd,mid-mx-i));
        print(ans);
    }
    return 0;
}

标签:Arrays,mn,mid,int,CF1550D,ans,Excellent,mx,mod
From: https://www.cnblogs.com/Spare-No-Effort/p/18010545

相关文章

  • 无涯教程-Passing arrays to 函数s
    下面的示例更好地解释了此概念。Passingarraystofunctions-示例varnames=newArray("Mary","Tom","Jack","Jill")functiondisp(arr_names){for(vari=0;i<arr_names.length;i++){console.log(names[i])......
  • [LeetCode] 2966. Divide Array Into Arrays With Max Difference
    Youaregivenanintegerarraynumsofsizenandapositiveintegerk.Dividethearrayintooneormorearraysofsize3satisfyingthefollowingconditions:Eachelementofnumsshouldbeinexactlyonearray.Thedifferencebetweenanytwoelementsin......
  • 无涯教程-Scala - 数组(Arrays)
    Scala提供了一种数据结构数组,它存储了相同类型元素的固定大小的顺序集合。声明数组要在程序中使用数组,必须声明一个变量以引用该数组,并且必须指定该变量可以引用的数组的类型。varz:Array[String]=newArray[String](3)orvarz=newArray[String](3)在此,z被声明为可容......
  • 15 Friendly Arrays
    FriendlyArrays打表#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;voidsolve(){ intn,m; cin>>n>>m; vector<int>a(n+1); vector<int>b(m+1); for(inti=1;i<=n;i++)cin>>a[i]; for(inti=1;i<......
  • 方法&Arrays_API总结
    总结方法方法的组成:修饰符+返回值类型+方法名+形参列表+方法体方法签名:方法名+形参列表调用方法:方法有static修饰,调用是:类名.方法名();调用方法使用参数是实际参数(必须是具体的数据)在java里面用static修饰的方法叫做:类方法或者静态方法形参和实参声明......
  • Arrays.asList方法返回对象
    上例子int[]arr={1,2,3};Listlist=Arrays.asList(arr);for(Objectobject:list){System.out.println(object);}可以看到输出的其实是一个对象,并不是1,2,3解决方法Integer[]arr={1,2,3};......
  • Arrays.asList的坑
    2023年12月21日下午16.46分,咪宝马上下班去上海过圣诞节去了,一个人孤单 CTO:谁在项目中使用Arrays.asList、ArrayList.subList,就立马滚蛋! 1.asList用来把数组转成ArrayList,方便。但问题是这个方法生成的ArrayList是Arrays的内部类,这个内部类没有实现抽象类AbstractList的......
  • CF1870B-Friendly-Arrays-题解
    title:CF1870BFriendlyArrays题解date:2023-09-2010:32:12categories:-题解翻译给出长度为\(n\)的序列\(a\)和长度为\(m\)的序列\(b\),选出\(b\)中的任意个数(可以不选),让\(a\)的每个数都或上它们,求\(a_1\oplusa_2\oplus\dots\oplusa_n\)的最大值......
  • Arrays工具类二分查找方法binarySearch方法详解​
    Arrays工具类二分查找方法binarySearch方法详解基础知识该方法的一般形式是publicstatic<T>intbinarySearch(T[]a,Tkey),对于基本类型,都有相应的重载方法,如针对int类型有binarySearch(int[]a,intkey)等。该方法的原理是使用二分查找算法在指定的数组中搜索指定的值。在调......
  • CF1859F Fancy Arrays
    FancyArrays-洛谷我们先找这题看起来有点奇怪的部分:\(x\leq40\)\(|a_i-a_{i-1}|\leqk\)我们先考虑第二个条件怎么用。我们发现\(\mina_i\in[0,x+k)\),而原数组相邻两数之差的条件肯定要考虑成差分来处理可以发现,一个差分数组和\(\mina_i\)与一个\(a_......