做网站搞笑口号,广州数商云,虾皮这种网站根本不值得做,重庆网站推广软件正题
题目链接:https://www.luogu.com.cn/problem/AT2161 题目大意
长度为nnn的0/10/10/1串#xff0c;mmm个区间#xff0c;你可以按照顺序任意排列区间中的数字#xff0c;求最后的可能情况数。 保证给出区间的左端点不降。 1≤n,m≤30001\leq n,m\leq 30001≤n,m≤3000…正题
题目链接:https://www.luogu.com.cn/problem/AT2161 题目大意
长度为nnn的0/10/10/1串mmm个区间你可以按照顺序任意排列区间中的数字求最后的可能情况数。 保证给出区间的左端点不降。
1≤n,m≤30001\leq n,m\leq 30001≤n,m≤3000 解题思路
先去掉一些没用区间然后空位补上长度为111的区间。 设fi,jf_{i,j}fi,j表示处理到第iii个区间并且到下一个区间前已经有jjj个一了。
然后每次枚举这段区间和下一段区间不交的部分放多少个一不难发现这个总复杂度是O(n)O(n)O(n)的。
时间复杂度O(n2)O(n^2)O(n2) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N3100,P1e97;
ll n,m,cnt,w[N],C[N][N],l[N],r[N],f[N][N];
char s[N];
signed main()
{scanf(%lld%lld,n,cnt);scanf(%s,s1);C[0][0]1;for(ll i1;in;i)w[i]w[i-1](s[i]1);for(ll i1;in;i)for(ll j0;ji;j)C[i][j](C[i-1][j](j?C[i-1][j-1]:0))%P;for(ll i1,L,R;icnt;i){scanf(%lld%lld,L,R);if(Rr[m])continue;else if(Ll[m])r[m]R;else{for(ll jr[m]1;jL;j)m,l[m]r[m]j;m;l[m]L;r[m]R;}}for(ll ir[m]1;in;i)m,l[m]r[m]i;l[m1]r[m1]n1;f[0][0]1;for(ll i1;im;i){ll ql[i1]-l[i],br[i]-l[i]1;for(ll j0;jl[i];j){ll sw[r[i]]-j,ts-(r[i]-l[i1]1);for(ll kmax(t,0ll);kmin(q,s);k)(f[i][jk]f[i-1][j]*C[q][k]%P)%P; }}printf(%lld\n,f[m][w[n]]);return 0;
}
