杭电第九场

1010题

1.题目大意:n个数。每次随机选两个数a,b合并成ab+a+b，直到剩下一个数为止。求剩下数字的期望，答案对998244353取模。

2.分析:当时列数据，最后猜测，期望应该为∑a+不同个数的数的乘积之和。

3.代码:

```#include <iostream>
#include <vector>
#include <map>
#pragma warning(disable:4996)
using namespace std;
#define ll long long
const int mod = 998244353;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        scanf("%d", &n);
        ll a[505];
        for (int i = 0; i < n; i++) {
            scanf("%lld", &a[i]);
        }
        for (int i = n - 1; i > 0; i--) {
            ll s = (a[i] % mod + a[i - 1] % mod) % mod;
            ll p = a[i] % mod * a[i - 1] % mod;
            a[i - 1] = (s + p) % mod;
        }
        printf("%lld\n", a[0]);
    }

    return 0;
}