[Comet1790]Ternary String Counting

令$f_{i,j,k}$表示前$i$个位置，三种字符最后一次出现的位置为$i,j$和$k$（保证$k<j<i$）的方案数

考虑转移（递推），即分为两步——

1.填写第$i$个字符，即从$f_{i-1,j,k}$转移到$f_{i,j,k},f_{i,i-1,j}$或$f_{i,i-1,k}$

2.考虑以$i$为右端点的区间，即仅保留$j\in [L_{j}(i),R_{j}(i)]$且$k\in [L_{k}(i),R_{k}(i)]$的位置（其余位置清0）

（关于$L/R_{j/k}(i)$显然可以$o(m)$预处理出）

暴力转移复杂度为$o(n^{3})$，考虑优化——

关于第一步，如果将$i$滚动，实际上修改的位置仅有$o(n)$个，而修改的值即某行/列的元素和，那么再额外维护该信息，同时修改也可以继续维护，复杂度降为$o(n^{2})$

关于第二步，注意到一个位置被清0后不会再有值，那么只需要快速找到需要清0且非0的位置，这可以对每行维护一个双向队列来实现，进而均摊复杂度也降为$o(n^{2})$

最终，总复杂度为$o(n^{2}+m)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 5005

 4 #define mod 1000000007

 5 deque<int>q[N];

 6 int t,n,m,l,r,x,ans,Lj[N],Rj[N],Lk[N],Rk[N],sr[N],sc[N],f[N][N];

 7 int read(){

 8     int x=0;

 9     char c=getchar();

10     while ((c<'0')||(c>'9'))c=getchar();

11     while ((c>='0')&&(c<='9')){

12         x=x*10+c-'0';

13         c=getchar();

14     }

15     return x;

16 }

17 void upd(int x,int y,int z){

18     q[y].push_back(x);

19     sr[x]=(sr[x]+z)%mod;

20     sc[y]=(sc[y]+z)%mod;

21     f[x][y]=(f[x][y]+z)%mod;

22 }

23 void clear_l(int y){

24     int x=q[y].front();

25     q[y].pop_front();

26     sr[x]=(sr[x]-f[x][y]+mod)%mod;

27     sc[y]=(sc[y]-f[x][y]+mod)%mod;

28     f[x][y]=0;

29 }

30 void clear_r(int y){

31     int x=q[y].back();

32     q[y].pop_back();

33     sr[x]=(sr[x]-f[x][y]+mod)%mod;

34     sc[y]=(sc[y]-f[x][y]+mod)%mod;

35     f[x][y]=0;

36 }

37 int main(){

38     t=read();

39     while (t--){

40         n=read(),m=read();

41         for(int i=1;i<=n;i++){

42             Lj[i]=Lk[i]=0;

43             Rj[i]=Rk[i]=i-1;

44         }

45         for(int i=1;i<=m;i++){

46             l=read(),r=read(),x=read();

47             if (x==1)Rj[r]=min(Rj[r],l-1);

48             if (x==2)Lj[r]=max(Lj[r],l),Rk[r]=min(Rk[r],l-1);

49             if (x==3)Lk[r]=max(Lk[r],l);

50         }

51         memset(sr,0,sizeof(sr));

52         memset(sc,0,sizeof(sc));

53         memset(f,0,sizeof(f));

54         for(int i=0;i<n;i++)q[i].clear();

55         upd(0,0,1);

56         for(int i=1;i<=n;i++){

57             for(int j=0;j<max(i-1,1);j++)upd(i-1,j,(sr[j]+sc[j])%mod);

58             for(int j=0;j<i;j++){

59                 if ((Lk[i]<=j)&&(j<=Rk[i])){

60                     while ((!q[j].empty())&&(q[j].front()<Lj[i]))clear_l(j);

61                     while ((!q[j].empty())&&(q[j].back()>Rj[i]))clear_r(j);

62                 }

63                 else{

64                     while (!q[j].empty())clear_l(j);

65                 }

66             }

67         }

68         ans=0;

69         for(int i=0;i<n;i++)

70             for(int j=0;j<n;j++)ans=(ans+f[i][j])%mod;

71         printf("%d\n",ans);

72     }

73     return 0;

74 }

巴特西

[Comet1790]Ternary String Counting

最新文章

热门文章