solution-contest2.26(div2)B

· · 个人记录

How to solve problem B without your brain

首先有一些很显然的性质，就是如果一个属性不同的球相撞，我们可以视为没发生这次碰撞。否则我们可以看成两个小球的属性发生了改变，但是方向依然不变，穿过去了。所以电荷的正负仅仅代表方向。

套路地，考虑没有 ? 怎么算一个给定序列的答案。我们考虑对于每一个 + 算他是否产生了贡献。发现需要维护当前所有还在往右走的小球的属性。手玩一下，不难把整个过程抽象成下面的过程：

我们会记给定序列的答案了。

首先，这个删除操作看起来非常蠢，所以我们不妨看作原来有一长串仅包含 A,B,? 的序列，然后有一个指针在上面向后移动。

赛时蠢笨了（摆烂了），如果你直接暴力考虑每一个 ? 或者 B 是否会产生贡献，暴力拆贡献直接算那就是 O(n^2) 的。

正确的做法应当是考虑每一个 ? 或者 A 是否被贡献。显然的，贡献条件是最终序列的 B 的个数要大于当前位置的下标。预处理组合数后缀和即可做到 O(n)。

总结：我是傻逼。自我感觉我这样子转换后就变得清晰多了。

// Problem: B. 弹性碰撞（physics）
// URL: http://www.gdfzoj.com:23380/contest/929/problem/8760
// Writer: WRuperD
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 2e6 + 10;
const int mod = 998244353;

int quickPower(int a, int b, int p){
    int base = a, ans = 1;
    while(b){
        if(b & 1)   ans *= base, ans %= mod;
        base *= base, base %= mod;
        b >>= 1;
    }
    return ans;
}
string s;
int fk[MAX], fk2[MAX];

int c2(int n, int m){
    if(n == m)  return 1;
    if(n <= 0)  return 0;
    if(m > n)   return 0;
    return fk[n] * fk2[m] % mod * fk2[n - m] % mod;
}

int fk3[MAX];

int fk4[MAX], fk5[MAX];

void solve(){
    cin>>s;
    int n = s.length(); 
    s = " " + s;
    fk[0] = 1;
    for(int i = 1; i < MAX; i++)    fk[i] = fk[i -1] * i % mod;
    fk2[MAX - 1] = quickPower(fk[MAX - 1], mod - 2, mod);
    for(int i = MAX - 2; i >= 0; i--){
        fk2[i] = fk2[i + 1] * (i + 1) % mod;
    }
    int tot2 = 0;
    for(int i = 1; i <= n; i++){
        if(s[i] == '?') tot2++;
    }
    // write(tot2), endl;
    fk3[0] = fk3[1] = 1;
    for(int i = 1; i < MAX; i++)    fk3[i] = fk3[i - 1] * 2 % mod;
    for(int i = tot2; i >= 0; i--){
        fk4[i] = fk4[i + 1] + c2(tot2, i);
        fk4[i] %= mod;
        fk5[i] = fk5[i + 1] + c2(tot2 - 1, i);
        fk5[i] %= mod;
    }
    int pre = 0, ans = 0;
    for(int i = 1; i <= n; i++){
        if(s[i] == '+') pre++;
    }
    // write(tot2), endl;
    // write(fk5[0]), endl;
    // write(fk4[0]), endl;
    for(int i = 1; i <= n; i++){
        if(s[i] == '-' or s[i] == '?'){
            // write(i - pre), put(), write(tot2 - (s[i] == '?')), endl;-
            if(i - pre > tot2 - (s[i] == '?'))  continue;
            // write(i), endl;
            if(s[i] == '-'){
                if(i <= pre)    ans += fk4[0 + s[i] == '?'];
                else ans += fk4[i - pre + (s[i] == '?')]; 
            }else{
                if(i <= pre)    ans += fk5[0];
                else ans += fk5[i - pre]; 
            }
            // write(ans), endl;
            ans %= mod;
        }
    }
    write(ans), endl;
    // int ans = 0;
    // int pos = 1;
    // int pre = 0;
    // for(int i = 1; i <= n; i++){
        // if(s[i] == '+' or s[i] == '?'){
            // for(int j = pos; j < i; j++){+-
                // if(j - pos > pre)    break;
                // if(s[j] == '-'){
                    // ans += c2(pre, j - pos) * fk3[tot2 - pre - (s[i] == '?')] % mod;
                    // ans %= mod;
                // }else if(s[j] == '?'){
                    // ans += c2(pre - 1, j - pos) * fk3[tot2 - pre - (s[i] == '?')] % mod;
                    // ans %= mod;
                // }
            // }
            // if(s[i] == '+'){
                // pos++;
            // }else{
                // pre++;
            // }
        // }
    // }
    // write(ans), endl;
}

signed main(){
    int t = 1;
    while(t--)  solve();
    return 0;
}