HDU-2825

题意：多组输入，每组给定n,m,k三个整数，一个长度为n的字符串，由m个子字符串中的至少k个组成，求一共有多少种排列组合方法，结果需要mod

解题思路:

ac自动机上跑状压DP

dp[i+1][nx][k|val[nx]] = (dp[i+1][nx][k|val[nx]]+dp[i][j][k])%mod

第一维表示当前主串长度，第二维表示自动机上的节点，第三维用二进制表示集合中存在哪几个字符串。需要利用辅助数组num预处理二进制下数字x的1的个数，即包含字符串的个数

代码：

//#pragma GCC optimize(3)#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      using namespace std;#define lowbit(x) x&(-x)typedef long long ll;typedef long double lb;typedef unsigned long long ull;int read();const double PI = acos(-1.0);const int maxn = 110;const int mod = 20090717;int n,m,cnt;int tot;struct node{ int nx[26]; int val; int fail;}ac[maxn];int num[1<<11];int dp[30][maxn][1<<10];//长度，节点，状态int ans;char s[50];void init(){ tot = 0; for(int i = 0;i

q; for(int i = 0;i<26;i++) { if(ac[0].nx[i]) { ac[ac[0].nx[i]].fail = 0; q.push(ac[0].nx[i]); } } while(!q.empty()) { int r = q.front(); q.pop(); ac[r].val|=ac[ac[r].fail].val; for(int i = 0;i<26;i++) { if(!ac[r].nx[i]) { ac[r].nx[i] = ac[ac[r].fail].nx[i]; }else { ac[ac[r].nx[i]].fail = ac[ac[r].fail].nx[i]; q.push(ac[r].nx[i]); } } }}int gao(){ memset(dp,0,sizeof(dp)); dp[0][0][0] = 1; for(int i = 0;i

=cnt) { for(int j = 0;j<=tot;j++) { ans = (ans+dp[n][j][i])%mod; } } } return ans%mod;}int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); getnum(); while(scanf("%d%d%d",&n,&m,&cnt)!=EOF) { if(n==0&&m==0&&cnt==0)break; init(); for(int i = 0;i

<< 3) + (x << 1) + (ch ^ 48); ch = getchar(); } return w ? -x : x;}

转载地址：https://www.cnblogs.com/cloudplankroader/p/11735977.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：codeforces-1385E(拓扑排序)

下一篇：面向纯小白的CLion(C++)基于Windows的安装配置教程

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

HDU-2825

题意：多组输入，每组给定n,m,k三个整数，一个长度为n的字符串，由m个子字符串中的至少k个组成，求一共有多少种排列组合方法，结果需要mod

解题思路:

发表评论

最新留言

关于作者

推荐文章