2020暑期集训1：DP强化

题目较多，知识点较杂，多为入门题。未完成

hdu多校1.1：Blank

ac代码

const int mod = 998244353;
const int N = 100+10;
const int M = 1e6+10;
/*=================================================================================*/

vector <pii> condition[N];
int dp[N][N][N][2];
int n, m, l, r, x, ans;

void init() {
   ans=0;
   dp[0][0][0][0] = 1;
   for1(i, n) condition[i].clear();
}

int main() {
   int tt; cin>>tt;
   while(tt--) {
      scanf("%d %d", &n, &m);
      init();
      for0(i, m) {
         scanf("%d %d %d", &l, &r, &x);
         condition[r].pb(pii(l, x));
      }
      for(int i=1, now=1; i<=n; ++i, now^=1) {
         for(int j=0; j<=i; ++j)
            for(int k=0; k<=j; ++k)
               for(int t=0; t<=k; ++t)
                  dp[j][k][t][now]=0;

         for(int j = 0; j < i; ++j) for(int k = 0; k <= j; ++k) for(int t = 0; t <= k; ++t) {
            dp[j][k][t][now] += dp[j][k][t][now^1]; dp[j][k][t][now] %= mod;
            dp[i-1][j][k][now] += dp[j][k][t][now^1]; dp[i-1][j][k][now] %= mod;
            dp[i-1][j][t][now] += dp[j][k][t][now^1]; dp[i-1][j][t][now] %= mod;
            dp[i-1][k][t][now] += dp[j][k][t][now^1]; dp[i-1][k][t][now] %= mod;
         }

         for(int j = 0; j < i; ++j) for(int k = 0; k <= j; ++k) for(int t = 0; t <= k; ++t) {
            for(auto tmp : condition[i]) {
               int cnt=1;
               if(j >= tmp.first) cnt++;
               if(k >= tmp.first) cnt++;
               if(t >= tmp.first) cnt++;
               if(cnt != tmp.second) dp[j][k][t][now] = 0;
            }
         }
      }
      int now = n&1;
      for(int j=0; j<n; ++j) for(int k=0; k<=j; ++k) for(int t = 0; t <= k; ++t) {
         ans += dp[j][k][t][now]; ans %= mod;
      }
      // debug1
      cout<<ans<<endl;
   }
   return 0;
}

int t, n, q;
ll r, s, x, a;
ll E[N];

ll Pow(ll l, ll r) {
   ll ans = 1;
   while(r) {
      if(r & 1) ans = ans*l % mod;
      l = l*l % mod;
      r>>=1;
   }
   return ans;
}

int main() {
   scanf("%d", &t);
   while(t--) {
      scanf("%d %d", &n, &q);
      for1(i, n) {
         scanf("%lld %lld %lld %lld", &r, &s, &x, &a);
         ll p = Pow(r, mod-2) * s % mod;
         E[i+1] = (E[i] + p*a%mod + (s-r)*Pow(r, mod-2)%mod * (E[i] - E[x] + mod)%mod) % mod;
      }
      while(q--) {
         ll l, r;
         scanf("%lld %lld", &l, &r);
         printf("%lld\n", (E[r] - E[l] + mod) % mod);
      }
   }
   return 0;
}