2021CCPC 威海 （dp + two points or NTT）

传送门

题解

\(E_{i}\)表示i次重开的期望值。

\(E_i = E_{i - 1} * P(random\_sum < E_{i - 1}) + E(random\_sum \geq E_{i - 1})\)

即如果当前随机的两张牌的和小于\(E_{i - 1}\)，则选择重开；否则不重开。有i次重开机会的期望就是重开的概率乘以i-1次重开的期望值，再加上不重开的期望。

开始想到一种NTT的做法，即用NTT算出两两之和的所有情况，因为\(max\{a_i\} \leq 10^6\)，所以两两的和不会超过\(2\times 10^6\)，时间复杂度为\(O(max\{a_i\}\log max\{a_i\} + max\{a_i\})\)。

但是这道题时限只给了1秒，我写的NTT最终还是T了。不过看到有同学写的FFT只用了600多ms就跑出来了，估计是NTT取模太慢了吧。

可以注意到这题k只给到了100，如果每次计算\(E_i\)时采用双指针的方式对重开的情况重新计算，时间复杂度为\(O(nk)\)。

但是NTT的做法也不是一无是处的，如果把这题的k改为\(10^5\)甚至更大，把时限稍微开大点，就只能NTT了。

code(NTT)

/*************************************************************************
> File Name: 1.cpp
> Author: Knowledge_llz
> Mail: 925538513@qq.com
> Blog: https://www.cnblogs.com/Knowledge-Pig/ 
************************************************************************/

#include
#define LL long long
#define endl '\n'
using namespace std;
const int N = 2097152, mod = 998244353;
const double eps = 1e-6;
LL n, Q, k, a[N + 100], b[N + 100], c[N + 100], dp[N + 100], lim;
double E[N + 100];
LL qpow(LL x, LL y){
    LL res = 1;
    while(y){
        if(y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
void ntt(LL *x, bool idft){
    for(int i = 1; i < lim; ++i)
        if(i < dp[i]) swap(x[i], x[dp[i]]);
    
    for(int i = 2; i <= lim; i <<= 1){
        LL w = qpow(3, (mod - 1) / i);
        int len = i / 2;
        if(idft) w = qpow(w, mod - 2);
        for(int k = 0; k < lim; k += i){
            LL p = 1;
            for(int l = k; l < k + len; ++l){
                LL tmp = p * x[len + l] % mod;
                x[len + l] = (x[l] - tmp + mod) % mod;
                x[l] = (x[l] + tmp) % mod;
                p = p * w % mod;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out","w", stdout);
#endif
    cin >> n >> k >> Q;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        ++b[a[i]];
    }
    for(lim = 1; lim < 2000000; lim <<= 1);
    for(int i = 1; i < lim; ++i)
        dp[i] = (dp[i >> 1] >> 1) | ((i & 1) ? lim >> 1 : 0);
    ntt(b, 0);
    for(int i = 0; i < lim; ++i) c[i] = b[i] * b[i] % mod;
    ntt(c, 1);
    LL inv = qpow(lim, mod - 2);
    for(int i = 0; i < lim; ++i) c[i] = c[i] * inv % mod;
    for(int i = 1; i <= n; ++i) --c[a[i] * 2];
    LL sum = (n - 1ll) * n; double ans = 0;
    for(int i = 0; i < lim; ++i) ans += c[i] * i;
    E[0] = ans / sum; LL num = 0;
    for(int i = 1, j = 0; i <= 100; ++i){
        while((E[i - 1] - j) > eps){
            ans += c[j] * (E[i - 1] - j);
            num += c[j++];
        }
        E[i] = ans / sum;
        ans += (E[i] - E[i - 1]) * num;
    }
    cout << fixed << setprecision(10) << E[k] << endl;
    while(Q--){
        int x, y, c;
        cin >> x >> y >> c;
        sum = a[x] + a[y];
        if(!c) cout << "accept" << endl;
        else if(fabs(sum - E[c - 1]) <= eps) cout << "both" << endl;
        else if(sum - E[c - 1] > eps) cout << "accept" << endl;
        else cout << "reselect" << endl; 
    }
    return 0;
}

code(two points)

/*************************************************************************
> File Name: 1.cpp
> Author: Knowledge_llz
> Mail: 925538513@qq.com
> Blog: https://www.cnblogs.com/Knowledge-Pig/ 
************************************************************************/

#include
#define LL long long
#define endl '\n'
using namespace std;
const int N = 3e5, mod = 998244353;
const double eps = 1e-6;
LL n, Q, k, a[N + 100], b[N + 100], c[N + 100], dp[N + 100], sum[N];
double E[N + 100];

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out","w", stdout);
#endif
    cin >> n >> k >> Q;
	double ans = 0; LL fm = (n - 1ll) * n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        b[i] = a[i];
		ans += a[i] * (n - 1ll) * 2ll; 
    }
	sort(b + 1,  b + n + 1);
	for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + b[i];
	E[0] = ans / fm;
    for(int i = 1; i <= 100; ++i){
		double x = ans;
        for(int l = 1, r = n; l <= n; ++l){
			while(r && b[l] + b[r] > E[i - 1]) --r;
			x -= (b[l] * r + sum[r]);
			if(l <= r) x += 2 * b[l];
			x += E[i - 1] * (r - (l <= r));
			// cout << l << " " << r << " " << x << endl;
		}
		E[i] = x / fm;
    }
    cout << fixed << setprecision(10) << E[k] << endl;
    while(Q--){
        int x, y, c;
        cin >> x >> y >> c;
        LL s = a[x] + a[y];
        if(!c) cout << "accept" << endl;
        else if(fabs(s - E[c - 1]) <= eps) cout << "both" << endl;
        else if(s - E[c - 1] > eps) cout << "accept" << endl;
        else cout << "reselect" << endl; 
    }
    return 0;
}