T1

会发现，如果说要删除掉某个区间内的所有字符，那么起两个端点中的最小值必须要小于这个区间内的最小值。

利用该系统进行dp即可。

#include
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=3e5+5,mod=1e9+7;
int n,a[maxn],dp[maxn],sum[maxn];
signed main()
{freopen("arrange.in","r",stdin);freopen("arrange.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];set >s;sum[0]=1;int res=0;for(int i=1;i<=n;i++){pairu;while(!s.empty()){u=(*s.rbegin());if(u.first>a[i]){res=(res-dp[u.second]+mod)%mod;s.erase(u);}else break;}if(s.empty()) dp[i]=sum[i-1];else dp[i]=(res+sum[i-1]-sum[u.second])%mod;if(dp[i]<0) dp[i]=(dp[i]+mod);sum[i]=(sum[i-1]+dp[i])%mod;s.insert({a[i],i});res=(res+dp[i])%mod;}int ans=0;for(auto x:s)ans=(ans+dp[x.second])%mod;cout<

T2

发现m很小，所以说我们只需要去将?定义成一种新的字符。

然后对他建trie，或者直接用暴搜枚举就行。

#include
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
map mp;
int ans=0,n,m;
void dfs1(string s,int x,int sum)
{if(x==m){mp[sum]++;return;}if(s[x]=='?') dfs1(s,x+1,sum*30+27); else dfs1(s,x+1,sum*30+s[x]-'a'),dfs1(s,x+1,sum*30+26); 
}
void dfs2(string s,int x,int sum)
{if(x==m){ans+=mp[sum];return;}if(s[x]=='?') dfs2(s,x+1,sum*30+26);else dfs2(s,x+1,sum*30+s[x]-'a');dfs2(s,x+1,sum*30+27);
}
signed main()
{freopen("word.in","r",stdin);freopen("word.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){string s;cin>>s;dfs2(s,0,0);dfs1(s,0,0);}cout<