首页 > 其他分享 >Different Subsets For All Tuples (数学)

Different Subsets For All Tuples (数学)

时间:2024-03-03 17:11:16浏览次数:25  
标签:Different Subsets sum pos len Tuples 然后 序列 我们

Different Subsets For All Tuples 数学

题面

有一个长度为\(n\)的数列,每个位置上数字的值在\([1,m]\)范围内,则共有\(m^n\)种可能的数列。分别求出每个数列中本质不同的子序列个数(包含空序列),然后求和,答案对\(10^9+7\)取模。(\(1\le n,m\le10^6\))

数据范围

$ 1<=n,m<=10^{6} $

解法

显然,我们需要求每个子序列的贡献,空序列的贡献很简单,就是\(m^n\)。然后我们处理非空的,但我们会发现,很容易重复,比如子序列1,在11这个序列中出现了两次,但其贡献显然只有1,那该如何处理呢?这里有一个非常实用且常用的技巧,就是我们把这个子序列的下标处理成一个字符串,我们只去计算每种序列里字典序最小的那个,这样就避免重复了。

于是我们应该怎么搞呢?首先我们把长度为\(len\)子序列的下标记为\(pos_1……pos_{len}\),然后把整个字符串分为两部分,第一部分是\(1—pos_{len}\),第二部分是剩下的。

对于第一部分,我们假设除开作为子序列的,还有\(a\)个字符位置,那么这些字符的选择只有\(m-1\)个,然后这个问题就转化成了把\(a\)个小球放到\(len\)个盒子里,且允许有空的,个数为\(C_{a+len-1}^{len-1}\)。

对于第二部分,我们就随便乱填,个数为\(m^{n-len-a}\)。

综上,我们得出一个式子,\(ans=\sum_{i=1}^{n}\sum_{j=0}^{n-i}C_{i+j-1}^{i-1}*(m-1)^{j}*m^{n-i-j}*m^i\)。这样子求就T飞了,于是我们想个办法化简一下。

首先换元,这一步我们要尽量让组合数的表达式简单点,因为那样才好看。

令k首先等于j+i,即第一部分的总长度。然后式子变为\(\sum_{i=1}^{n}\sum_{k=i}^{n}C_{k-1}^{i-1}*(m-1)^{k-i}*m^{n-k+i}\)。

然后还是不好看,\(k-1\)变成\(k\),\(i-1\)变成\(i\)。

式子变为\(\sum_{i=0}^{n-1}\sum_{k=i}^{n-1}C_{k}^{i}*(m-1)^{k-i}*m^{n-k+i}\)

换限,\(\sum_{k=0}^{n-1}*\sum_{i=0}^{k}*C_{k}^{i}*(m-1)^{k-i}*m^i*m^{n-k}\)

然后根据二项式定理,我们注意到\(C_{k}^{i}*(m-1)^{k-i}*m^i\)其实就是\((m+m-1)^k\)

所以原式化为\(\sum_{k=0}^{n-1}(2m-1)^k*m^{n-k}\)

然后我们就能很快的求出来了。

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int mod=1e9+7;
void solve(){
    int n,m;cin>>n>>m;
    vector<ll>a(n+1);vector<ll>b(n+1);
    a[0]=1,b[0]=1;
    ll ans=0;
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]*(2ll*m-1ll)%mod;
        b[i]=b[i-1]*m%mod;
    }
    for(int i=0;i<n;i++)ans=(ans+(a[i]*b[n-i]%mod)%mod);
    cout<<(ans+b[n])%mod<<"\n";
}
signed main(){
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    srand((unsigned)time(NULL));
    //int t;std::cin>>t;while(t--)
    solve();
}

标签:Different,Subsets,sum,pos,len,Tuples,然后,序列,我们
From: https://www.cnblogs.com/shi5/p/18050319

相关文章

  • AT_abc169_f Knapsack for All Subsets题解
    如果我们定义\(dp[i][j]\)表示对于前i个字符而言,其子集满足条件的个数。那4么对于一个位置i而言,要么选择它贡献要么不选择,所以\(dp[i][j]=dp[i-1][j-a[i]](j>=a[i])+dp[i-1][j]\),这是每一个\(f(i)\)的函数。然后我们加上所有的\(dp[i][k](i:1到n)ans+=dp[i][k......
  • CF1921D Very Different Array 题解
    补充一个对本题贪心思路更(?)清楚的解释。本题贪心思路:在\(a_i,b_i\)分别升序的情况下,对于每个\(a_i\),与它差值最大的\(b_i\)只可能出现在\(b_{n-i+1}\)与\(b_{m-i+1}\)这两者中。证明:首先,假设我们有一个长度为\(n\)的升序序列\(s\)。则对于\(s_1\),与它差值最大......
  • Differential Equations
    Firstorderdifferentialequations:$\frac{{\rmd}y}{{\rmd}x}+Fy=G$​$$\begin{aligned}&\frac{{\rmd}y}{{\rmd}x}+Fy=G\qquadz\frac{{\rmd}y}{{\rmd}x}+Fzy=Gz\qquadz\frac{{\rmd}y}{{\rmd}x}+\frac{{\rmd}z}{{\rmd}x}y=\frac{{\rmd......
  • D. Find the Different Ones!
    前言拿到题目首先看数据量,n,q都是2e5的数量级,如果是暴力解的话时间复杂度会达到O(m*n)(最差情况m次询问,每次l和r为1和n),很明显会超时。这就意味着我们要在线性的时间内完成查询,即每次询问的查询时间保证在O(1)。题解准备一个数组b存储该连续相同数字串的起始点,然后我们从左向右遍历......
  • C. Choose the Different Ones!
    题解我们只需要遍历1~k,这时会有四种情况:1、只存于a数组中。2、只存于b数组中。3、同时存于ab数组中。4、不存在于ab数组中。对于情况三,这种数我们不需要去管,因为它可以算在任意的数组上。那么我们只需要判断情况一和二的数是否都<=k/2,并且情况一二三的数总和为k.Code ......
  • D. Find the Different Ones!
    原题链接核心\(p[i]\)代表离\(a[i]\)最近的不同元素code#include<bits/stdc++.h>usingnamespacestd;inta[200005]={0};intp[200005]={0};intmain(){intt;cin>>t;while(t--){intn;cin>>n;for(inti=1......
  • CF1408F Two Different 题解
    解题思路先考虑如何将一堆数变为相同的。显然,这里有一个条件\(n=2^k,k\in\mathbbZ\),证明如下:每次操作只能将两个数变为相同的,那么一个数在使得其他数变为相同数的操作中(我们不妨将所有数进行这种操作称为一轮操作),一个数最多被使用一次;按照错位操作,即第一轮\(1\)和\(2\)......
  • 无涯教程-Swift - 元组(Tuples)
    Swift4还引入了Tuples元组类型,该类型用于将多个值组合在单个复合值中,元组中的值可以是任何类型,并且不必是同一类型。如,("LearnFK",123)是一个具有两个值的元组,一个值是字符串Type,另一个是整数类型。这是元组声明的语法-varTupleName=(Value1,value2,…anynumberofval......
  • 无涯教程-Scala Tuples函数
    Scala元组将固定数量的项目组合在一起,以便它们可以作为整体传递。与数组或列表不同,元组可以容纳不同类型的对象,但它们也是不可变的。以下是一个包​​含整数,字符串和控制台的元组的示例。valt=(1,"hello",Console)以下是语法糖-valt=newTuple3(1,"hello",Console)元......
  • D. Very Different Array
    原题链接题解,太抽象了最优情况一定可以是这样:Code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lla[200005]={0};llb[200005]={0};lll[200005]={0},r[200005]={0};intmain(){cin.tie(0);cout.tie(0);llt;cin>>t;w......