【CF1043D】Mysterious Crime（贡献）

题意：给定m个人，每个人有n个数字且每个人的所有数字都是一个n的排列，求有多少种方案去掉某个前缀和后缀后m个人剩余的部分相等

m<=10,n<=1e5

思路：考虑极长的一段连续匹配的串，因为最后需要是连续的一段，所以它对答案的贡献应该是它的子串个数

刚开始以为是子序列个数还傻乎乎的去写高精了，也算是一个教训吧

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<queue>

 #include<vector>

 #include<ctime>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N  110000

 #define M  130

 #define MOD 1000000007

 #define eps 1e-8

 #define pi acos(-1)

 int a[][N],b[][N],n,m;

 int isok(int x,int y)

 {

     //if(x==0) return 1;

     for(int i=;i<=m;i++)

      if(b[i][x]!=b[i][y]-) return ;

     return ;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

      for(int j=;j<=n;j++)

      {

          scanf("%d",&a[i][j]);

          b[i][a[i][j]]=j;

      }

     a[][]=;

     ll ans=;

     ll len=;

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

      if(isok(a[][i-],a[][i])) len++;

       else

       {

               //printf("len=%lld\n",len);

               ans+=(len+)*len/;

               len=;

       }

     //printf("len=%lld\n",len);

     ans+=(len+)*len/; 

     printf("%lld\n",ans);

     return ;

 }

巴特西

【CF1043D】Mysterious Crime（贡献）

最新文章

热门文章