ABC310F Make 10 Again 题解

· · 题解

来一个极为暴力的做法。

首先注意到大于 10 的数都没用。于是

设 dp_{i,a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10}} 表示到第 i 个数，1 有 a_1 个，2 有 a_2 个，……，10 有 a_{10} 个的概率。由于我们要凑 10 ，因此对我们有用的状态满足 a_1\leq 10,a_2\leq 5,a_3 \leq 3,a_4,a_5\leq 2,a_6,a_7,a_8,a_9,a_{10}\leq 1 ，因此时间和空间都绰绰有余。对于每次扔骰子操作，直接暴力枚举扔出来的哪个数（如果扔出来的数 \ge 11 可以一起计算），转移即可。最后直接枚举所有状态暴力 \operatorname{check} 更新答案。时间复杂度 \mathcal{O}(n) ，常数在 8\times 10^5 左右，在 AT 的少爷姬上绰绰有余。

高能代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110;
const int mod=998244353;
int qpow(int x,int b){
    int res=1;
    while(b){
        if(b&1) res=res*x%mod;
        x=x*x%mod;
        b>>=1;
    }
    return res;
}
int n,a[N];
int inv(int x){return qpow(x,mod-2);}
void to(int& x,int y){x=(x+y)%mod;}
int dp[N][11][6][4][3][3][2][2][2][2][2];
bool check(int _1,int _2,int _3,int _4,int _5,int _6,int _7,int _8,int _9,int _0){
    return _0||(_9&&_1)||(_8&&(_2||_1>=2))||(_7&&(_3||_2&&_1||_1>=3))||(_6&&(_4||_3&&_1||_2>=2||_2&&_1>=2||_1>=4))
    ||(_5&&(_5>=2||_4&&_1||_3&&_2||_3&&_1>=2||_2>=2&&_1||_2&&_1>=3||_1>=5))||(_4&&(_4>=2&&_2||_4>=2&&_1>=2||_3>=2||_3&&_2&&_1
    ||_3&&_1>=3||_2>=3||_2>=2&&_1>=2||_2&&_1>=4||_1>=6))||(_3&&(_3>=3&&_1||_3>=2&&_2>=2||_3>=2&&_2&&_1>=2||_3>=2&&
    _1>=4||_2>=3&&_1||_2>=2&&_1>=3||_2&&_1>=5||_1>=7))||(_2&&(_2>=5||_2>=4&&_1>=2||_2>=3&&_1>=4||_2>=2&&_1>=6||_1>=8))
    ||_1>=10;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    dp[0][0][0][0][0][0][0][0][0][0][0]=1;
    for(int i=0;i<n;i++){
      for(int _1=0;_1<=10;_1++){
        for(int _2=0;_2<=5;_2++){
          for(int _3=0;_3<=3;_3++){
            for(int _4=0;_4<=2;_4++){
              for(int _5=0;_5<=2;_5++){
                for(int _6=0;_6<=1;_6++){
                  for(int _7=0;_7<=1;_7++){
                    for(int _8=0;_8<=1;_8++){
                      for(int _9=0;_9<=1;_9++){
                        for(int _0=0;_0<=1;_0++){
                          int cur=dp[i][_1][_2][_3][_4][_5][_6][_7][_8][_9][_0];
                          int invi=inv(a[i+1]);
                          if(a[i+1]>=11) to(dp[i+1][_1][_2][_3][_4][_5][_6][_7][_8][_9][_0],cur*invi%mod*(a[i+1]-10)%mod);
                          if(a[i+1]>=1) to(dp[i+1][min(_1+1,10ll)][_2][_3][_4][_5][_6][_7][_8][_9][_0],cur*invi%mod);
                          if(a[i+1]>=2) to(dp[i+1][_1][min(_2+1,5ll)][_3][_4][_5][_6][_7][_8][_9][_0],cur*invi%mod);
                          if(a[i+1]>=3) to(dp[i+1][_1][_2][min(_3+1,3ll)][_4][_5][_6][_7][_8][_9][_0],cur*invi%mod);
                          if(a[i+1]>=4) to(dp[i+1][_1][_2][_3][min(_4+1,2ll)][_5][_6][_7][_8][_9][_0],cur*invi%mod);
                          if(a[i+1]>=5) to(dp[i+1][_1][_2][_3][_4][min(_5+1,2ll)][_6][_7][_8][_9][_0],cur*invi%mod);
                          if(a[i+1]>=6) to(dp[i+1][_1][_2][_3][_4][_5][min(_6+1,1ll)][_7][_8][_9][_0],cur*invi%mod);
                          if(a[i+1]>=7) to(dp[i+1][_1][_2][_3][_4][_5][_6][min(_7+1,1ll)][_8][_9][_0],cur*invi%mod);
                          if(a[i+1]>=8) to(dp[i+1][_1][_2][_3][_4][_5][_6][_7][min(_8+1,1ll)][_9][_0],cur*invi%mod);
                          if(a[i+1]>=9) to(dp[i+1][_1][_2][_3][_4][_5][_6][_7][_8][min(_9+1,1ll)][_0],cur*invi%mod);
                          if(a[i+1]>=10) to(dp[i+1][_1][_2][_3][_4][_5][_6][_7][_8][_9][min(_0+1,1ll)],cur*invi%mod);
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
    int ans=0;
      for(int _1=0;_1<=10;_1++){
        for(int _2=0;_2<=5;_2++){
          for(int _3=0;_3<=3;_3++){
            for(int _4=0;_4<=2;_4++){
              for(int _5=0;_5<=2;_5++){
                for(int _6=0;_6<=1;_6++){
                  for(int _7=0;_7<=1;_7++){
                    for(int _8=0;_8<=1;_8++){
                      for(int _9=0;_9<=1;_9++){
                        for(int _0=0;_0<=1;_0++){
                          int cur=dp[n][_1][_2][_3][_4][_5][_6][_7][_8][_9][_0];
                          if(check(_1,_2,_3,_4,_5,_6,_7,_8,_9,_0)) //cerr<<"! "<<_1<<" "<<_2<<" "<<_3<<" "<<_4<<" "<<_5<<" "<<_6<<" "<<_7<<" "<<_8<<" "<<_9<<" "<<_0<<" "<<cur<<endl,
                          to(ans,cur);
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    printf("%lld\n",ans);
}