QAQ球结QAQ

学术版

zyxzyx100219 @ 2024-11-28 13:39:48

题目描述

有 𝑛 堆果子，分别有 𝑎1 , 𝑎2 , ⋯ , 𝑎𝑛 个果子。一次合并分为有顺序的 𝑛 − 1 步，每一步选择两堆果子，合并成一堆。

定义一次合并的权值为每一步被合并的两堆果子数量之积的和。求出每一种合并方法的权值之和对998244353取模的结果。

两种合并方式不同当且仅当有一步被合并的两堆不同。即使有两堆的果子数量相同，我们仍然把它们视为不同的两堆。

输入格式

第一行一个正整数 𝑛。第二行 𝑛 个非负整数，依次表示 𝑎1 , ⋯ , 𝑎𝑛。

输出格式

一行一个非负整数，表示所有合并方法权值之和（对 998244353 取模）。

样例

样例输入1 2

100001 100002

样例输出1

17856472

样例解释1

只能合并 1 步，即合并仅有的两堆。两堆果子数量之积为 100001 ∗ 100002 = 10000300002，对 998244353 取模的结果为 17856472。

注意合并 (𝐴, 𝐵) 和 (𝐵, 𝐴) 视为相同的合并方式。

样例输入2

1 2 3

样例输出2

by zyxzyx100219 @ 2024-11-28 15:41:30

@Mr_Az 啊没有啊

by acb437 @ 2024-11-28 17:25:29

模拟赛 T1？方案数是 \prod^n_{i=2}C_i^2。

by acb437 @ 2024-11-28 17:26:39

@zyxzyx100219 自己思考一下，每次选两堆合并，又是有顺序的，所以直接组合数累乘就可以了。

by zyxzyx100219 @ 2024-11-28 17:38:17

@acb437 式子对了。。大样例不对

by acb437 @ 2024-11-28 17:52:42

@zyxzyx100219 注意取模和 long long。你每一种方案的贡献算对了吗？代码发出来看看。

by zyxzyx100219 @ 2024-11-28 17:56:57

#include<bits/stdc++.h>
using namespace std;
long long a[100001];
long long fans[100001]; 
int n;
int mod=998244353;
int main()
{
    //freopen("fft.in","r",stdin);
    //freopen("fft.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    } 
    long long ans=0;
    for(int i=1;i<n;i++)
    {
        long long x=a[i]*a[i+1]%mod;
        a[i+1]+=a[i];
        a[i+1]%=mod;
        ans+=x;
        ans%=mod;
    }

    fans[1]=1;
    fans[2]=1;
    fans[3]=3;
    for(int i=4;i<=n;i++)
    {
        fans[i]=fans[i-1]*((i*(i-1))/2%mod);
        fans[i]%=mod;
    }
    ans%=mod;
    cout<<ans*fans[n]%mod;
    return 0;
 }

by zyxzyx100219 @ 2024-11-28 17:57:15

@acb437

by acb437 @ 2024-11-28 18:26:11

@zyxzyx100219 算 fans 的循环 i 开 long long 之后就过了

by acb437 @ 2024-11-28 18:27:24

// ubsan: undefined
// accoders
#include<bits/stdc++.h>
using namespace std;
long long a[100001];
long long fans[100001]; 
int n;
int mod=998244353;
int main()
{
    freopen("fft.in","r",stdin);
    freopen("fft.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    } 
    long long ans=0;
    for(int i=1;i<n;i++)
    {
        long long x=a[i]*a[i+1]%mod;
        a[i+1]+=a[i];
        a[i+1]%=mod;
        ans+=x;
        ans%=mod;
    }
    fans[1]=1;
    fans[2]=1;
    fans[3]=3;
    for(int i=4;i<=n;i++)
    {
        fans[i]=fans[i-1]*((1ll*i*(i-1))/2%mod); //这里
        fans[i]%=mod;
    }
    ans%=mod;
    cout<<ans*fans[n]%mod;
    return 0;
 }

by zyxzyx100219 @ 2024-11-28 18:41:41

@acb437 谢谢dalao ORZ ORZ

上一页 |