排列组合或容斥原理 SPOJ

题目链接： https://vjudge.net/contest/237052#problem/H

这里给你一串数字，让你计算同时拥有这串数字最大值和最小值的子集（连续）和子序列（可以不连续）的数量，计算子串的数量是为了避免重复，我们可以从前往后扫描，前面的子集不能包括后面的，后面的可以包括前面的，我们每次记录最小值和最大值的位置t1，t2，起初把t1，t2设为0，每当遇到最大值或最小值是就把t1或t2的值变成最小值或最大值的下标，然后sum=sum+min（t1，t2），我也是刚刚看别人博客才知道的，举个例子：

2 1 4 3 2 1 　　min=1，max=4，t1=0，t2=0；

i=1, t1=0,t2=0,sum=min（0,0）+sum=0;

i=2, t1=2,t2=0,sum=min（2,0,）+sum=0；

i=3, t1=2,t2=3,sum=min（2,3）+sum=2，有2 1 4和1 4

i=4, t1=2,t2=3,sum=min（2,3）+sum=4, 有2 1 4 3和1 4 3

i=5, t1=2,t2=3,sum=min（2,3）+sum=6,有2 1 4 3 2和1 4 3 2

i=6, t1=6,t2=3,sum=min（6,3）+sum=9,有2 1 4 3 2 1和1 4 3 2 1 和4 3 2 1

然后我们要求子序列的话可以用两种方法求，一种是排列组合，我们在上面求子集数量时同时求最大值和最小值的数量，因为可能会多次出现，分别设为min_num,max_num，那我们如果要用排列组合算的话就是（2^min_num-1）*（2^max_num-1）*2^（n-min_num-max_num），自己揣摩一下，然后用容斥原理的话就是所有情况-没有最大值的情况-没有最小值的情况+没有最大值和最小值的情况

看代码

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

const ll inf=0xffffff;

const ll mod=;

ll n,m,k,t;

ll num[];

ll cal(ll a,ll b)

{

    ll ans=;

    while(b)

    {

        if(b&)

        ans=ans*a%mod;

        a=a*a%mod;

        b>>=;

    }

    return ans;

}

int main()

{

    cin>>t;

    while(t--)

    {

        cin>>n;

        ll min1=inf,max1=,min_num=,max_num=;

        ll sum1=,sum2=;

        for(int i=;i<=n;i++)

        {

            cin>>num[i];

            min1=min(min1,num[i]);

            max1=max(max1,num[i]);

        }

        if(min1==max1)

        {

            sum1=n*(n+)/%mod;

            sum2=cal(,n)-;

            cout<<sum1<<' '<<sum2<<endl;

            continue;

        }

        ll t1=,t2=;

        for(int i=;i<=n;i++)

        {

            if(min1==num[i])

            {

                t1=i;

                min_num++;

            }

            if(max1==num[i])

            {

                t2=i;

                max_num++;

            }

            sum1=(min(t1,t2)+sum1)%mod;

        }

        sum2=((cal(,min_num)-)%mod*(cal(,max_num)-)%mod*cal(,n-max_num-min_num))%mod;//排列组合

        /*sum2=(cal(2,n)-cal(2,n-max_num)-cal(2,n-min_num)+cal(2,n-max_num-min_num))%mod;//容斥原理

        if(sum2<0)

        sum2+=mod;*/

        cout<<sum1<<' '<<sum2<<endl;

    }

    return ;

}

巴特西

排列组合或容斥原理 SPOJ - AMR11H

最新文章

热门文章