[ARC100-F][DP]Colorful Sequences-白红宇

[ARC100-F][DP]Colorful Sequences

阅读量：92 次

发布时间：2019-02-26

本文共 3200 字，大约阅读时间需要 10 分钟。

翻译

给你 $K$ 和 $m$ ，给出一个长度为 $m$ 的由 $[1, K]$ 组成的序列
问用 $[1, K]$ 组成的长度为 $n$ 的好序列中有多少个如上给出的序列
定义一个序列为好序列当且仅当其有一个长度为 $K$ 的子串，满足 $[1, K]$ 在其中各出现了一次

题解

gank英文题解现场
~~begay的题解太难懂了…~~
正难则反
考虑用在所有序列中的数量减去在非法序列中的情况
第一个答案就是 $K^{n-m}(n-m+1)$
第二种答案我们分情况讨论
1：若给出的序列是个好序列，此时不存在他在非法序列中的情况，直接输出即可
对于以下两种情况，先考虑一个子问题的求法
如何求长度为 $i$ ，末尾存在长度为 $j$ 的序列满足其中的数两两不同，但 $j + 1$ 就存在相同了的序列个数
设 $d p [i] [j]$ 表示如上，考虑转移至 $d p [i + 1] [k]$
若 $k\leq j$ ，显然贡献仅有 $1$
若 $k = j + 1$ ，显然我们后面能填的数有 $K - j + 1$ 个，贡献为 $K - j + 1$
其余贡献为 $0$
转移用一个前缀和优化掉即可
2：给出的序列满足数两两不同
此时求一个问题的答案，即所有非法序列中长度为 $m$ 的满足两两不同的序列个数和
出来之后除掉一个 $\frac{k!}{(k-m)!}$ 即可
这个问题可以用上面的 $d p$ 完成，注意记录一个 $g [i] [j]$ 表示长度为 $m$ 的序列数
3：剩余情况
我们求出其前缀最长有多长满足两两不同，后缀最长有多长满足两两不同
然后可以发现的是，我们前面填的东西与后面填的东西是完全不影响的
那么就枚举一下串的位置，用上面的 $d p$ 数组计数即可
具体可以看代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #define LL long long#define mp(x,y) make_pair(x,y)#define pll pair
              
               #define pii pair
               
                using namespace std;inline int read(){ int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar();} return x*f;}int stack[20];inline void write(int x){ if(x<0){ putchar('-');x=-x;} if(!x){ putchar('0');return;} int top=0; while(x)stack[++top]=x%10,x/=10; while(top)putchar(stack[top--]+'0');}inline void pr1(int x){ write(x);putchar(' ');}inline void pr2(int x){ write(x);putchar('\n');}const int MAXN=25005;const int MAXM=405;const int mod=1e9+7;int pow_mod(int a,int b){ int ret=1; while(b) { if(b&1)ret=1LL*ret*a%mod; a=1LL*a*a%mod;b>>=1; } return ret;}int f[MAXN][MAXM],s[MAXM],s1[MAXM],g[MAXN][MAXM];int n,K,m,a[MAXN];int pre[MAXN],inv[MAXN];LL ans;bool check1(){ int cnt=0; if(m
                
                 K)return false; memset(s,0,sizeof(s)); for(int i=1;i<=m;i++) { s[a[i]]++; if(s[a[i]]>1)return false; } return true;}void ad(int &x,int y){ x+=y;if(x>=mod)x-=mod;}int C(int n,int m){ return 1LL*pre[n]*inv[m]%mod*inv[n-m]%mod;}void solve2(){ memset(s,0,sizeof(s)); s[0]=s1[0]=f[0][0]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=min(i,K);j++) { ad(f[i][j],s[j]);ad(f[i][j],1LL*f[i-1][j-1]*(K-j+1)%mod); ad(g[i][j],s1[j]); ad(g[i][j],1LL*g[i-1][j-1]*(K-j+1)%mod); if(j>=m)ad(g[i][j],f[i][j]); } for(int j=K-1;j>=0;j--)s[j]=(s[j+1]+f[i][j])%mod,s1[j]=(s1[j+1]+g[i][j])%mod; } int sum=0; for(int i=1;i
                 
                  1){ ln1=i-1;break;} } memset(s,0,sizeof(s)); for(int i=m;i>=1;i--) { s[a[i]]++; if(s[a[i]]>1){ ln2=m-i;break;} } int sum=0; for(int i=ln1;i-ln1+1+m-1<=n;i++) { int s1=0,s2=0; for(int j=ln1;j
                  
                   =0;i--)inv[i]=1LL*inv[i+1]*(i+1)%mod; n=read();K=read();m=read(); for(int i=1;i<=m;i++)a[i]=read(); ans=1LL*pow_mod(K,n-m)*(n-m+1)%mod; if(check1())return pr2(ans),0;//colorful if(check2())solve2(); else { memset(s,0,sizeof(s)); s[0]=f[0][0]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=min(i,K);j++) { ad(f[i][j],s[j]); ad(f[i][j],1LL*f[i-1][j-1]*(K-j+1)%mod); } s[K]=0; for(int j=K-1;j>=0;j--)s[j]=(s[j+1]+f[i][j])%mod; } solve3(); } return 0;}