A-Holy
思路
由于要让最小值最大，不难想到二分答案。二分后将原矩阵中大于等于 \(mid\) 的值设为 \(1\)，小于的设为 \(0\)，然后将每一行压成二进制，存在两行满足要求当且仅当两行或起来等于 \(2^m-1\)。因此对于每一行 DFS 每个位置上是 \(0\) 还是 \(1\)。复杂度 \(\Theta(2^m n\log a_i)\)。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,l=1e9+7,r;
int a[300005][10];
int b[300005][10];
int t[260],a1,a2;
int now[20];
void dfs(int r,int x,int sum,int num)
{
if(x==m+1)
{
if((sum|num)==(1<<m)-1&&t[sum]) a1=r,a2=t[sum];
return;
}
if(now[x]) dfs(r,x+1,sum*2,num);
dfs(r,x+1,sum*2+1,num);
}
bool check(int x)
{
memset(t,0,sizeof(t));
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++)
{
int sum=0;
for(int j=1;j<=m;j++)
{
sum=sum*2+(a[i][j]>=x);
}
t[sum]=i;
}
for(int i=1;i<=n;i++)
{
int sum=0;
for(int j=1;j<=m;j++)
{
sum=sum*2+(a[i][j]>=x);
now[j]=(a[i][j]>=x);
}
if(sum==(1<<m)-1)
{
a1=i,a2=i;
return 1;
}
int l1=a1,l2=a2;
dfs(i,1,0,sum);
if(l1!=a1||l2!=a2) return 1;
}
return 0;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%lld",&a[i][j]);
l=min(l,a[i][j]);
r=max(r,a[i][j]);
}
}
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
{
l=mid+1;
}
else r=mid-1;
}
if(a1&&a2) printf("%lld %lld",a1,a2);
else puts("1 1");
return 0;
}
B-damn
分析
容易发现可以把初始序列在前面反着复制一遍，即变成 \(a_n,a_{n-1},a_{n-2},\dots,a_1,a_1,a_2,a_3,\dots,a_n\)，原问题就转化成了求在这个新序列上的最长上升子序列长度及方案数。拿线段树维护以每个数结尾的最长长度，支持单点修改，区间求 \(\max\)，区间求 \(\max\) 个数即可。假设在新串上的方案数是 \(ans\)，长度是 \(len\)，原问题的答案就是 \(2^{n-len-1}ans\)，因为剩下 \(n-len\) 个可以随便放在左右，还要除以 \(2\)，因为第一个放左放右都一样。
核心代码
int n,a[MAXN],b[MAXN],tr[MAXN<<2],cnt[MAXN<<2],dp[MAXN];
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
inline void pup(int p){
if(tr[ls]>tr[rs]) cnt[p]=cnt[ls],tr[p]=tr[ls];
else if(tr[ls]==tr[rs]) cnt[p]=(cnt[ls]+cnt[rs])%mod,tr[p]=tr[ls];
else cnt[p]=cnt[rs],tr[p]=tr[rs];
}void upd(int p,int l,int r,int x,int c,int k){
if(l==r){
if(tr[p]<c) cnt[p]=k,tr[p]=c;
else if(tr[p]==c) (cnt[p]+=k)%=mod;
}else{
if(x<=mid) upd(ls,l,mid,x,c,k);
else upd(rs,mid+1,r,x,c,k);pup(p);
}
}Pair que(int p,int l,int r,int L,int R){
if(L>R) return Pair(0,0);
if(L<=l&&r<=R) return Pair(cnt[p],tr[p]);
else{
Pair res=Pair(0,0);
if(L<=mid){
Pair tmp=que(ls,l,mid,L,R);
res.first=tmp.first;res.second=tmp.second;
}if(R>mid){
Pair tmp=que(rs,mid+1,r,L,R);
if(res.second<tmp.second) res.first=tmp.first,res.second=tmp.second;
else if(res.second==tmp.second) (res.first+=tmp.first)%=mod;
}return res;
}
}int qpow(int b,int p){
int res=1;
while(p){
if(p&1) res=(res*b)%mod;
p>>=1;b=(b*b)%mod;
}return res;
}signed main(){
qread(n);int i,j;for(i=1;i<=n;i++) qread(a[i]),b[i]=a[i];for(i=n+1;i<=(n<<1);i++) a[i]=a[i-n];
for(i=1;i<=n;i++) a[i]=b[n-i+1];n<<=1;for(i=1;i<=n;i++) b[i]=a[i];sort(b+1,b+1+n);
int t=unique(b+1,b+1+n)-b-1;for(i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+t,a[i])-b;
for(i=1;i<=n;i++){
Pair tmp=que(1,1,t,1,a[i]-1);
upd(1,1,t,a[i],tmp.second+1,qmax(1ll,tmp.first));
}Pair ans=que(1,1,t,1,t);n>>=1;
int tmp=ans.second==n?(ans.first>>1):ans.first*qpow(2,n-ans.second-1)%mod;
printf("%lld %lld\n",ans.second,tmp);
return 0;
}
C-beachy
分析
发现两个区间相似当且仅当两个区间离散化之后的排列长度相等，且这两个区间出现位置相同。
考虑所有长度为 \(i\) 的排列的贡献 \(ans\)：
首先选出 \(i\) 个数有 \(n\choose i\) 种方案，另外的 \(n-i\) 个数可以随便排，方案数 \((n-i)!\)，再把排列插到这 \(n-i\) 个数形成的 \(n-i+1\) 个空隙中，设 \(f_{i,j}\) 表示长度为 \(i\) 的排列，逆序对总数不大于 \(j\) 的数量，则有：
\[ans=\sum\limits_{i=1}^n({n\choose i}(n-i)!)^2(n-i+1)f_{i,m} \]，剩下的问题就集中在如何计算 \(f\) 上，首先发现长度为 \(n\) 的序列逆序对数最多有 \(\dfrac{n(n-1)}{2}\) 对，于是最大只需计算到 \(j=\dfrac{n(n-1)}{2}\)。
容易得出：
\[f_{i,j}=\sum\limits_{k=j-i+1}^j f_{i-1,k} \]，前缀和优化即可。
核心代码
int T,n,m,dp[MAXN][MAXM],fac[MAXN],inv[MAXN],up;
int qpow(int b,int p){
int res=1;
while(p){
if(p&1) res=(res*b)%mod;
p>>=1;b=(b*b)%mod;
}return res;
}inline int C(int x,int y){return fac[x]*inv[y]%mod*inv[x-y]%mod;}
inline void init(int sz){
fac[0]=1;for(int i=1;i<=sz;i++) fac[i]=(fac[i-1]*i)%mod;
inv[sz]=qpow(fac[sz],mod-2);for(int i=sz-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
}void pre(int n=501){
init(MAXN-3);int i,j;up=n*n/2;
for(i=0;i<=n;i++) dp[i][0]=1;
for(i=1;i<=n;i++){
int all=((i*(i-1))>>1);
for(j=1;j<=up;j++){
if(j<=all) dp[i][j]=(dp[i-1][j]-(j-i>=0?dp[i-1][j-i]:0)+mod)%mod;
(dp[i][j]+=dp[i][j-1])%=mod;
}
}
}signed main(){
qread(T);int i,j;pre();
while(T--){
qread(n,m);int ans=0;m=qmin(up,m);
for(i=1;i<=n;i++)
(ans+=C(n,i)*fac[n-i]%mod*C(n,i)%mod*fac[n-i]%mod*dp[i][m]%mod*(n-i+1)%mod)%=mod;
printf("%lld\n",ans);
}
return 0;
}
D-sheet
分析
有这样三种图：
第一种我们只需要用一个简单环覆盖就好了，第二种和第三种我们需要两条简单路径覆盖。
设一个环的度数是这个环的环外边的数量
我们还可以像这样来理解：
第二种，我们在覆盖那条环外边的时候顺便覆盖了环内的一些边，但可惜此时还差一条边
第三种，我们可以在覆盖两条环外边的时候顺手就把整个环给覆盖掉，所以可以认为是说这个环不存在贡献了，这个环被我们删掉了
也就是说，只要一个环的度数 \(\geq 2\)，那么它就可以在环外边被覆盖的时候一块被覆盖。
在度数为 \(0/1\) 的时候，需要额外的一费
现在假装所有环都被覆盖了，变成了一个无向无环图
考虑这样几种情况：
考虑每个点的贡献，即为了覆盖于这个点有关联的边所付出费用
图一中，每个点贡献 \(1\) ，一条边两个端点，除 \(2\)。
图二中，度数为 \(2\) 的点贡献为 \(0\)。
图三中，每个点贡献 \(1\)，可以看做隔离左侧三个点，先做一次图二操作，把左上点和下点缩到了中心点上，然后变成了图一情况，此时中心点有贡献 \(1\)。一条边两个端点，除 \(2\)。
图四中，中心点无贡献
我们于是得到这样的一个规律：
偶度数点贡献 \(0\)，奇度数点贡献 \(1\)，最后将总贡献除 \(2\) 即可
找环可以用 tarjan，复杂度 \(\Theta(n)\)
Ex-math
分析
这其实是高次的韦达定理。
设 \(x_1,x_2,\dots,x_n\) 为方程的 \(n\) 个根，于是有：
\[a_n(x-x1)(x-x2)\dots(x-x_n)=0 \]，展开等号左边的式子得到：
\[a_nx^n-a_n(x_1+x_2+\dots+x_n)+\dots+(-1)^n a_nx_1x_2\dots x_n=0 \]，发现变成了和原式类似的形式，显然 \(\sum\limits_{i=1}^nx_i=-\dfrac{a_{n-1}}{a_n},\prod\limits_{i=1}^n x_i=(-1)^n\dfrac{a_0}{a_n}\)。
标签：cnt,int,题解,sum,tr,20221102,ans,模拟,mod From： https://www.cnblogs.com/lxy-2022/p/20221102-mo-ni-sai-ti-jie.html