mod=10**9+7
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
for i in range(m+1):
    dp[0][i]=1
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1])%mod
        else:
            dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1]-dp[i][j])%mod
print(dp[n][m])

Jour 7

ABC131-E Friendships

Temps pris

Cela a pris plus de 40 minutes et je ne pouvais pas AC, alors j'ai expliqué AC

Cause d'erreur

Je ne pouvais pas trier les modèles typiques de construction de graphiques.

Considération

** Pour le moment, j'ai décidé de dessiner divers graphiques et de les rechercher de manière découvrable **, mais je ne pouvais pas facilement construire la logique. À la suite de l'expérience, lorsqu'il y a des côtés entre tous les sommets, le nombre de paires de sommets dont la distance la plus courte est 2 est 0, donc le nombre de paires de sommets dont la distance la plus courte est 2 en réduisant les côtés un par un. J'ai essayé de trouver un moyen d'augmenter un par un. Aussi, à ce moment, je ne savais pas qu'un graphe concaténé nécessiterait un minimum de $ N-1 $, mais ** je me suis perdu **.

(Ce qui suit est une considération après avoir vu l'explication, etc.)

Tout d'abord, il semble qu'il est facile de faire une politique qui ** dans un problème de construction où le cas minimum et le cas maximum sont décidés, le cas minimum et le cas maximum sont considérés et il peut être bien configuré entre eux **. En d'autres termes, s'il y a des arêtes entre tous les sommets, K sera le minimum (0), alors considérons le cas où c'est le maximum.

Ici, ** les graphes concaténés nécessitent des arêtes $ N-1 $ et la distance la plus courte entre leurs sommets est 1 **, donc $ K> \ frac {N (N-1)} {2 } - (N-1) = \ frac {(N-1) (N-2)} {2} $ Un graphe concaténé ne peut pas être construit. Par conséquent, on s'attend à ce que $ K $ soit le maximum à ** $ K = \ frac {(N-1) (N-2)} {2} $ . Ici, en considérant un graphe (en étoile) ayant une arête entre le sommet 1 et tout autre sommet, entre deux sommets autres que le sommet 1 ($ \ frac {{(N-1)} {(N) -2)}} {2} $ way) La distance la plus courte est 2 et vous pouvez construire un graphe concaténé qui satisfait $ K $ ( Shortest pour augmenter la distance entre les sommets où la distance la plus courte est 2) Il peut être plus facile de penser que ** éliminant l'espace entre les sommets avec une distance supérieure à 3).

Ensuite, ** envisagez d'augmenter les côtés un par un à partir du graphe en étoile et de diminuer les sommets avec la distance la plus courte de 2 un par un , mais en reliant les côtés entre deux sommets qui ne sont pas reliés par les côtés () Vous pouvez réduire la distance entre les sommets de un sans affecter la distance la plus courte entre les autres sommets **). En outre, la raison pour laquelle cela n'affecte pas la distance entre les deux autres sommets est que la distance la plus courte entre les deux sommets est de 1 ou 2 dans le graphique avec quelques côtés ajoutés au graphique en étoile, donc le changement de la distance la plus courte est de 2 lorsque les côtés sont ajoutés. Parce que c'est seulement 1.

A partir de ce qui précède, le graphe du sujet est construit en effectuant l'opération d'augmentation des arêtes de $ \ frac {{(N-1)} \ times {(N-2)}} {2} -k $ fois à partir de l'état du graphe en étoile. pouvez.

De plus, ** il semble préférable de se souvenir des graphiques typiques qui ont des formes distinctes lors de la création de graphiques **. Les trois suivants sont particulièrement célèbres.

<détails>

n,k=map(int,input().split())
if k>(n-1)*n//2-(n-1):
    print(-1)
else:
    ans=[(1,i) for i in range(2,n+1)]
    lestnum=(n-1)*n//2-(n-1)-k
    for i in range(2,n):
        for j in range(i+1,n+1):
            if lestnum!=0:
                ans.append((i,j))
                lestnum-=1
    print(len(ans))
    for i in ans:
        print(" ".join(map(str,i)))

//Pour l'optimisation du compilateur
#pragma GCC optimize("O3")
//Comprendre(Ordre alphabétique)
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
//pour la relation de boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ll(x.size()) //taille à la taille_Changement de t à ll
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire
#define Umap unordered_map
#define Uset unordered_set

signed main(){
    ll n;cin>>n;
    vector<ll> a(n);REP(i,n)cin>>a[i];
    multiset<ll> colors;
    colors.insert(a[0]);
    FOR(i,1,n-1){
        auto ne=colors.lower_bound(a[i]);
        if(ne==colors.begin()){
            colors.insert(a[i]);
        }else{
            colors.erase(--ne);
            colors.insert(a[i]);
        }
    }
    cout<<SIZE(colors)<<endl;
}