首页 > 其他分享 >Tyler and Strings ( 组合数学结论+根据数学式子来dp维护+字典序小) longlong 那个范围问题

Tyler and Strings ( 组合数学结论+根据数学式子来dp维护+字典序小) longlong 那个范围问题

时间:2022-11-02 15:25:36浏览次数:59  
标签:序小 longlong int long num 数学 ans ri dp

 

思路:

  • 遇到字典序 一般就是要 从左边到右边一个一个贪心的比较,    //////////// 边界条件. 
  • 于是由此DP, dp[i],表示i之前都是一样的 i 这个地方比他bi 小的 种类数
  • 关键是 后面这个 有重复元素的组合情况: 
  • 结论 有n个数 然后 有些数是重复的, 他的组合情况是: n!/num[i]..... 就是除以每一个数出现次数的阶层即可
  • 递推维护这个式子
  • 少一个数, 就是 *num[i]/n (当前个数) n--, 
  • 在更新 选一个数比ti小时, 就 先/n, 在看 这些比ti小的数的个数和, 利用树状数组维护
  • 把他变成一样的时候, 同理维护 
#include <bits/stdc++.h>
using namespace std;
#define ri register int 
#define M 2000005

int n,m;
long long  num[M],p[M],t[M];
const int mod=998244353;

long long  inv[M];
long long ksn(long long  a,long long b)
{
    long long ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        b>>=1;a=a*a%mod;
    }
    return ans;
}
long long ans=1;
int  val[M];
void add(int a)
{
    while(a<=2e5)
    {
        val[a]++;
        a+=a&(-a);
    }
}
void del(int a)
{
    while(a<=2e5)
    {
        val[a]--;
        a+=a&(-a);
    }
}
int qu(int a)
{
    int ans=0;
    while(a>=1)
    {
        ans+=val[a];
        a-=a&(-a);
    }
    return ans;
}
long long inv2[M];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>n>>m;
    for(ri i=1;i<=n;i++)
    {
        cin>>p[i];
        num[p[i]]++;
        add(p[i]);
    }
    for(ri i=1;i<=m;i++) cin>>t[i];
    
    for(ri i=1;i<=n;i++)
    {
        ans=ans*i%mod;
        inv[i]=ksn(ans,mod-2);
    }

    for(ri i=1;i<=n;i++)
    {
        inv2[i]=ksn(i,mod-2);
    }
    for(ri i=1;i<=200000;i++)
    {
       if(num[i])       /////////////////////// i  nong cheng = p[i]
       {
           ans=ans*inv[num[i]]%mod;
    
       }
    }

    long long ans2=0;
    long long  cnt=n;
    for(ri i=1;i<=min(n,m);i++)
    {
        long long tmp=qu(t[i]-1);
    
        ans2+=tmp*ans%mod*inv2[cnt]%mod;
        ans2%=mod;
        if(num[t[i]]==0) break; 
        del(t[i]);
        ans=ans*inv2[cnt]%mod*num[t[i]]%mod;
        num[t[i]]--;
        cnt--;
        if(i==min(n,m))
        {
            if(n<m) ans2=(ans2+ans)%mod;
        }
    }
    cout<<ans2;
    
    
    
}
View Code

后记:

  • i 不要 弄成p[i], 搞一个乌龙
  • 边界(包含左和右)条件特判

 

标签:序小,longlong,int,long,num,数学,ans,ri,dp
From: https://www.cnblogs.com/Lamboofhome/p/16851077.html

相关文章

  • 大数数学
    序数定义\[0=\emptyset\]\[n+1=n\cup\{n\}\]\[\alpha\le\beta=\alpha\subseteq\beta\]\[\exists\omega:0\in\omega,n\in\omega\impliesn+1\in\omega\]\[\supX=\b......
  • 000001 BC 数学函数
    <?phpheader('Content-Type:text/html;charset=utf-8');include'./assets/php/head.php';//BC数学函数/***bcadd—2个任意精度数字的加法计算*bccomp—......
  • Codeforces - 1391C - Cyclic Permutations(思维 + 组合数学 + 数论 + 图论、*1500)
    1391C-CyclicPermutations(⇔源地址)目录1391C-CyclicPermutations(⇔源地址)tag题意思路AC代码错误次数:0tag⇔思维、⇔组合数学、⇔数论、⇔......
  • 高等数学瞎学
    就是瞎学。极限两个重要极限\[\lim_{x\to0}{\sinx\overx}=1\]\[\lim_{x\to\infty}{\left(1+\frac{1}{x}\right)^x}=e\]几个常用等价无穷小\[\sinx\simx......
  • 数学
    哥德巴赫猜想任何一个大于\(2\)的偶数均可表示成为两个素数之和。最少交换次数如果我们想让一个数组a等于数组b,最少交换次数为n-2,n为环的个数边定义为如果我......
  • PyTorch: 张量的变换、数学运算及线性回归
    本文已收录于Pytorch系列专栏:​​Pytorch入门与实践​​专栏旨在详解Pytorch,精炼地总结重点,面向入门学习者,掌握Pytorch框架,为数据分析,机器学习及深度学习的代码能力打下......
  • 重磅综述 | 神经网络机器学习的数学理解
    本文是由鄂维南院士、马超、吴磊和StephanWojtowytsch2020年12月发表在CSIAMTransactionsonAppliedMathematics上的综述文章。原文题目为“TowardsaMathematicalU......
  • 机器学习1:基础部分:人工智能数学基础第1讲:行列式(一)
    文章目录​​学习目标:线性代数一:行列式​​​​学习内容:​​​​1.二阶与三阶行列式​​​​二阶行列式的计算-对角线法则​​​​举例​​​​三阶行列式的计算-对角线法则......
  • 机器学习3:基础部分:人工智能数学基础第1讲:行列式(二)
    文章目录​​学习目标:线性代数一:行列式​​​​学习内容​​​​4.对换​​​​定义​​​​兑换与排列奇偶性的关系​​​​补充定理​​​​例子​​​​小结​​​​5.行......
  • 高等数学介绍
    高等数学:架构图:详细介绍:  ......