Codeforces Round #572 (Div. 1)

序:

  • 最近没事写写CF玩…

T1 咕咕咕

T2 Count Pairs

题面:

  • You are given a prime number p, n integers a_1,a_2,…,a_n, and an integer k.
  • Find the number of pairs of indexes (i,j) (1≤i for which (a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p.

翻译:

  • 只要是人都能看懂…

分析:

  • 题目主要难在(a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p..
  • 我们其实看这个式子,进行一些小操作就可以很好的求出来…
  • 我们给左右两边都乘上(a_i – a_j)
  • 那么式子就变成(a_i^4 + a_j^4) \equiv k*(a_i-b_j) \bmod p
  • 然后移项,式子就成了:
    (a_i^4 – k*a_i) \equiv (b_j^4 – k\ast b_j) \bmod p
  • 接下来直接用map求每一种数字出现多少次就好了..

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=3e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());   
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
LL n,p,k,a[N],ans;
map<LL,int> Map;
signed main()
{
    read(n),read(p),read(k);
    for(int i=1;i<=n;i++) read(a[i]); 
    for(int i=1;i<=n;i++) Map[(a[i]*a[i]%p*a[i]%p*a[i]%p-k*a[i]%p+p)%p]++;
    for(map<LL,int>::iterator it=Map.begin();it!=Map.end();it++)
        ans+=(*it).second*((*it).second-1)/2;
    printf("%lld\n",ans);
    return 0;
}

T3 Array Beauty

题面:

  • Let’s call beauty of an array b_1,b_2,…,b_n (n>1) => \min\limits_{1 \leq i < j \leq n} |b_i - b_j|.
  • You’re given an array a_1,a_2,…a_n and a number k. Calculate the sum of beauty over all subsequences of the array of length exactly k. As this number can be very large, output it modulo 998244353.
  • A sequence a is a subsequence of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements.

翻译:

  • 给出一个序列,从中取出k个数,对于所有情况,其美丽度是所有元素间差绝对值的最小值,然后我们要把所有美丽度加起来输出…

分析:

  • 拿到这道题目,我们最先想到是怎么快速的求出每一个方案的美丽度,但是,我们并求不出…
  • 怎么办呢,看题解就好了…
  • 我们发现我们使用dp,可以在O(n)时间内求出最小值大于等于某个数的方案个数…
  • 那么我们发现一个大问题,如果从1开始算,一个美丽度为t的方案会被算到t次,而美丽度最大不过1000000/n个…然后就艹了…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=3e5+10;
const LL mod=998244353;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());   
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
LL n,m,ans,a[1010];
LL dp[1010][1010],sum[1010][1010];
LL solve(int x,int ret=0)
{
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) dp[i][j]=sum[i][j]=0;
    for(int i=1;i<=n;i++) dp[1][i]=1;
    for(int i=1;i<=m;i++)
    {
        int now=1;
        for(int j=1;j<=n;j++)
        {
            while(a[j]-a[now]>=x) now++;
            dp[i][j]=(dp[i][j]+sum[i-1][now-1])%mod;
            sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
        }
    }
    for(int i=1;i<=n;i++) (ret+=dp[m][i])%=mod;
    return ret;
}
signed main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=(a[n])/(m-1);i++) (ans+=solve(i))%=mod;
    printf("%lld\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注