CF1000D 又一個序列上的問題

2021-02-17 智子筆記
1 CF1000D 又一個序列上的問題題目連結：https://codeforces.com/problemset/problem/1000/d2 題目描述

時間限制

如果

如果一個序列可以分成正數個好的序列，則稱其為好序列。每個好的序列應該是序列的一個子段，並且序列的每個元素都應該完全屬於一個序列。例如，

對於給定的序列，計算其為好序列的子序列的數量，並模

3 題解

我們設

那麼如何計算這一部分答案呢？我們發現：在後面找到的好序列一定是某個

在這裡解釋一下這個轉移：由於

至於組合數，我們可以在開頭利用

代碼（空格警告）：

#include <iostream>
using namespace std;
const int N = 1e3+10;
const int mod = 998244353;
#define int long long
int n, ans;
int a[N], dp[N], c[N][N];
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) c[i][i] = 1, c[i][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            c[i][j] = (c[i-1][j] % mod + c[i-1][j-1] % mod) % mod;
        }
    }
    for (int i = n; i >= 1; i--)
    {
        if (a[i] <= 0) continue;
        if (n - i >= a[i])
        {
            for (int j = i+2; j <= n; j++)
            {
                dp[i] = (dp[i] + (c[j-i-1][a[i]] * dp[j] % mod) % mod) % mod;
            }
            dp[i] = (dp[i] + c[n-i][a[i]]) % mod;
        }
    }
    for (int i = 1; i <= n; i++) ans = (ans + dp[i]) % mod;
    cout << ans;
    return 0;
}
歡迎關注

相關焦點

  • 雖然你看過,但就是寫不出來系列-最長上升(下降)子序列並輸出子序列
    任何疑問、意見、建議請公眾號留言或聯繫qq474356284    給定一個無序的整數數組，找到其中最長上升子序列的長度。
  • 測試時間序列的40個問題
    時間序列分析是統計學的一個分支，廣泛應用於計量經濟學和運籌學等領域。這篇技能測試文章是為了測試你對時間序列概念的了解程度。共有1094人報名參加了這次技能測試。這個測試是為了測試你對時間序列的了解的水平。如果你錯過了這次技能測試，這裡有一些問題和對應的解決方案。如果你錯過了實時測試，也可以通過閱讀本文以了解你有多少題目是可以正確回答的。
  • CF613B 技能
    玩家根據一個叫做原力的大小來排名，原力就是一個玩家下面值的累加和。我們不如換一個思路：由於答案是由兩部分組成的，所以對於當前答案，我們可以將第一部分固定（枚舉使得當前情況第一部分值為定值），找到符合條件的最大的第二部分，並與最大值之間取
  • 動態規劃解最長公共子序列問題
    1 最長公共子序列問題概述1.1 問題定義序列如果存在一個序列2 動態規劃求解最長公共子序列問題C以及輔助矩陣 * 輸入是兩個序列*/void LCS::writeTable(Seq* seq1,Seq* seq2){    // 此處有一個小技巧，擴展了一行一列，由於後面會出現C[i-1][j] C[i][j-1]，擴展一行一列可以避免下標出現-1    int len1=seq1->len+1;    int len2=seq2->
  • python在Keras中使用LSTM解決序列問題
    p=8461時間序列預測是指我們必須根據時間相關的輸入來預測結果的問題類型。時間序列數據的典型示例是股市數據，其中股價隨時間變化。 遞歸神經網絡（RNN）已被證明可以有效解決序列問題。特別地，作為RNN的變體的長期短期記憶網絡（LSTM）當前正在各種領域中用於解決序列問題。序列問題的類型序列問題可以大致分為以下幾類：一對一：其中有一個輸入和一個輸出。
  • 如何使用XGBoost模型進行時間序列預測
    XGBoost也可以被用於時間序列預測，儘管它需要將時間序列數據集先轉換成監督學習問題。它需要用到一種被稱為前進式驗證的特殊方法來評估模型，因為使用k折驗證來評估模型容易導致偏向樂觀的結果。本教程中，你將探索如何為時間序列預測開發一個XGBoost模型。
  • 最長的Zig-Zag交替子序列問題
    最長的交替(Zig-Zag)子序列問題是找到給定序列的最長子序列的長度，以使該子序列中的所有元素交替出現。;22>9<49>31<60子序列{10, 22, 9, 50, 31, 60}滿足 10<22>9<50>31<60算法分析我們還是通過動態編程的方法來解決這個問題。
  • [STATA] 時間序列模型 - ARIMA檢驗
    2.（前面三種模型，d=0，即平穩時間序列模型不需要做差分）ARCH - Auto Regressive Conditional Heteroskedasticity, 自回歸條件異方差模型，用來解決傳統計量經濟學對時間序列變量的第二個假設（變異數恆定）所引起的問題；GARCH - Generalized Auto Regressive
  • 利用ARIMA構建高性能時間序列模型(附Python代碼)
    簡記為ARIMA（p,d,q），名稱為差分整合移動平均自回歸模型。ARIMA的實際就是差分運算與ARMA模型的組合，這意義關係重大，這說明任何非平穩序列如果能夠通過適當階數的差分實現差分後平穩，就可以對差分序列進行ARMA擬合了。而ARMA模型的分析方法非常成熟，這意味著對差分平穩序列的分析也將是非常簡單、非常可靠的。
  • 發放1000萬元消費券 南京湯山邀您來玩
    字號變大| 字號變小 19cf102b06e14f698ce323dd0b3a27e8
  • 時間序列模型matlab代碼 - CSDN
    你是否想要做時間序列分析，但卻不知道代碼怎麼寫？你是否不清楚時間序列分析各種模型該在什麼情況下使用？本文將針對以上兩個問題，帶你入門時間序列分析~等等！Women>等華納出品的電影每分鐘的觀看量，預估艾倫秀不同播出計劃的未來收視率和收入等等等等~~~剛入職的第一個月每天愁眉不展，時間序列的方法很多，很多時候，即使理論基礎學懂了，但是到實踐上，R裡的code要怎麼寫又是個大問題，網上的很多教程，教授了公式，卻不教授具體的代碼怎麼寫。
  • 線段的分型構成與特徵序列
    d1g1d2g2d3g3…dngn（其中di代表第i個底，gi代表第i個頂）。如果找到i和j，j>=i+2,使得dj<=gi,那麼稱向上線段被筆破壞。對於從向下一筆開始的，其中的分型構成這樣的序列：g1d1g2d2…gndn（其中di代表第i個底，gi代表第i個頂）。如果找到i和j，j>=i+2,使得gj>=di,那麼稱向下線段被筆破壞。
  • 時間序列問題上的可解釋機器學習的benchmark方法
    今天這篇文章介紹一篇機器學習可解釋的文章，該篇文章主要提出了一種時間序列問題上的機器學習可解釋方法的benchmark。文章連結：https://arxiv.org/abs/2010.13924雖然目前可解釋方法研究不成熟，但本篇文章我個人覺得還是比較有意思的，值得一看。
  • 如何用XGBoost做時間序列預測?終於有人講明白了
    完成本教程後，你將知道：XGBoost是用於分類和回歸問題的梯度提升集成方法的一個實現。通過使用滑動時間窗口表示，時間序列數據集可以適用於有監督學習。在時間序列預測問題上，如何使用XGBoost模型進行擬合、評估、預測。讓我們開始吧！
  • R語言時間序列函數大全(收藏!)
    #時間序列數據的顯示#zoo和xts都只能按照原來的格式顯示，timeSeries可以設置顯示格式print(x, format= 「%m/%d/%y %H:%M」) #%m表示月，%d表示天，%y表示年，%H表示時，%M表示分鐘，%A表示星期，%j表示天的序號
  • 一個奇怪的素數序列
    一個好奇的人類可以詢問關於素數的第一個問題是有多少，並且最早的證據之一是有無數多個素數是歐幾裡德元素的可愛論證。歐幾裡得的證明以有限的素數列表開始，並描述了一種生成不在列表中的素數的方法。為了找到下一個數字，我們乘以2×3並加1得到7，這是素數。繼續：2×3×7 + 1 = 43，也是素數。2×3×7×43 + 1 = 1807，即13×139。Euclid-Mullin序列是開始2,3,7,43,13等的序列：第一個術語是2，每個後續術語是1的最小素因子加上所有先前術語的乘積。