牛客練習試合22-C簡単でたらめ(bitset最適化dp)

タイトルリンク:https://www.nowcoder.com/acm/contest/132/C
タイトルの説明
全部でn個の数で、i番目の数はxです.
i 
x
i
 
[lを取ることができる.
i
, r
i
]のフィールドに表示されます.
 
S種類数を求める.0 <=n, li, ri <= 100.
入力

5
1 2
2 3
3 4
4 5
5 6

しゅつりょく

26

あなたにいくつかの段の序列の初期値と终わりの値をあげて、各段の序列は1つの値を取って、Sを値の平方和にして、siはSの値の集合にして、siの大きさを闻きます.
分析:bitsetで、(bitset解説リンク:https://blog.csdn.net/GodJing007/article/details/81044000)はbitset配列f[i]で結果を格納し、各f[I][j]について、I個のシーケンスが加算された場合、jの値がsi集合にあるか否かを表す.
状態遷移方程式:
                                                          
f[I] |= f[I-1] << num*num;
なぜbitsetを使うのですか?bitsetの異和のため、左シフトは集合を並べて、平方の加算を容易かつ効率的に表すことができる.時間の複雑さを著しく低減する.
コードは次のとおりです.

#include
using namespace std;
   
const int N=105;
bitset<1000005>f[N];
int main()
{
    int n,l,r;
    cin>>n;
    f[0][0]=1;   //       ，0 si 。
    for(int i=1;i<=n;i++)
    {
        cin>>l>>r;
        for(int j=l;j<=r;j++)
            f[i]|=f[i-1]<