2023.4.12拷逝

# T1 seq

首先这道题要注意对题意的理解，子序列的意思是子集，而不是子区间。

我们可以将序列从小到大排序。排序后，如果一个子序列只有 $a[i]$ ， $a[j]$ $(i<j)$ 和任意多个在 $a[i]$ 和 $a[j]$ 之间的数，那么这个子序列的权值就是 $a[i]\times a[j]$ 。这样的序列有 $2^{j-i-1}$个。

由此可知， $1-i$ 中包含 $i$ 的所有子序列（不包括只有 $a[i]$ 一个数的子序列）的权值和为$(2^{i-2}\times a[1]+2^{i-3}\times a[2]+...+a[i-1])\times a[i]$。令 $sum=2^{i-2}\times a[1]+2^{i-3}\times a[2]+...+a[i-1]$ ，在遍历这个序列的时候，可以通过 $sum=sum\times 2+a[i-1]$ 来更新 $sum$ ，用 $ans=ans+a[i]\times sum$ 来更新 $ans$ 。

$code:$

```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long mod=998244353;
long long p[1000005],n,a[1000005],ans,sum;
int main(){
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    p[0]=1;
    for(int i=1;i<=n;++i)
        p[i]=p[i-1]*2%mod;
    for(int i=1;i<=n;++i){
        sum=(sum*2%mod+a[i-1]%mod)%mod;
        ans=(ans+a[i]*sum%mod)%mod;
        ans=(ans+a[i]*a[i]%mod)%mod;
    }
    printf("%lld\n",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}
```

# T2 game

图的形态只有两种，一种是初始形态，另一种是边权全部取反的形态，所以可以考虑分层图。