CF572_Div2_F

╰半夏微凉° 2021-10-29 13:32 291阅读 0赞

# 题意 #

[http://codeforces.com/contest/1189/problem/F][http_codeforces.com_contest_1189_problem_F]

--------------------

# 思考 #

由于是子序列，答案只跟选法有关，与顺序无关，先排序。

直接计算答案比较困难。联想到期望的无穷级数计算公式，设gi表示beauty值大于等于i的总方案数，则答案=sigma(g1~max\{a\})。

对于给定的gi，这是容易得到答案的。使用前缀和优化能在O(nk)的时间中得到一个值。

再发现当gi较大时，没有任何合法的方案。因为k\*(n-1)会大于最大的值，取g到max\{a\}/(k-1)即可获得所有非0答案。

总复杂度O(max\{a\}\*n)。

--------------------

# 代码 #

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #pragma GCC optimize 2
     2 #include<bits/stdc++.h>
     3 #define mod 998244353
     4 using namespace std;
     5 typedef long long int ll;
     6 const int maxn=1E3+5; 
     7 int n,k,a[maxn],maxx,where[maxn];
     8 ll f[maxn][maxn],sum[maxn][maxn];
     9 ll get(int x)
    10 {
    11     for(int i=0;i<=k;++i)
    12         for(int j=0;j<=n;++j)
    13             f[i][j]=0;
    14     for(int i=1;i<=n;++i)
    15     {
    16         where[i]=where[i-1];
    17         while(a[i]-a[where[i]+1]>=x)
    18             ++where[i];
    19     }
    20     f[0][0]=1;
    21     for(int i=0;i<k;++i)
    22     {
    23         sum[i][0]=f[i][0];
    24         for(int j=1;j<=n;++j)
    25             sum[i][j]=(sum[i][j-1]+f[i][j])%mod;
    26         for(int j=1;j<=n;++j)
    27             f[i+1][j]=sum[i][where[j]];
    28     }
    29     ll sum=0;
    30     for(int i=1;i<=n;++i)
    31         sum=(sum+f[k][i])%mod;
    32     return sum;
    33 }
    34 int main()
    35 {
    36     ios::sync_with_stdio(false);
    37     cin>>n>>k;
    38     for(int i=1;i<=n;++i)
    39     {
    40         cin>>a[i];
    41         maxx=max(maxx,a[i]);
    42     }
    43     sort(a+1,a+n+1);
    44     ll ans=0;
    45     for(int i=1;i<=100000/(k-1)+10;++i)
    46         ans=(ans+get(i))%mod;
    47     cout<<ans<<endl;
    48     return 0;
    49 }

转载于:https://www.cnblogs.com/GreenDuck/p/11143851.html

[http_codeforces.com_contest_1189_problem_F]: http://codeforces.com/contest/1189/problem/F
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/771f488015054491afd51564a405f07f.png