参考资料：

　　[1]:（提取码：ppi6）

 

B.generator 1(矩阵快速幂)

•题意

　　已知 $f_{i}=af_{i-1}+bf_{i-2}$;

　　输入 f₀,f₁,a,b,n,mod；

　　求 f_n%mod ；

•题解

　　习题；

　　首先将递推式转化为矩阵乘法表达式：

　　$\left( \begin{array}{cc} f_{i} \\ f_{i-1} \end{array}\right)=\left( \begin{array}{cc} a&b \\ 1&0 \end{array}\right)\cdot\left( \begin{array}{cc} f_{i-1} \\ f_{i-2} \end{array}\right)$

　　不妨令 $\mathbf{A_{i}} =\left( \begin{array}{cc} f_{i} \\ f_{i-1} \end{array}\right)$ , $\mathbf{T} =\left( \begin{array}{cc} a&b \\ 1&0 \end{array}\right)$;

　　那么，原式可化为 $A_{i}=T\cdot A_{i-1}=T^{2}\cdot A_{i-2}= \cdots = T^{i-1}\cdot A_{1}$;

　　处理完递推式后，是不是就大功告成了？

　　no,no,no;

　　还差最后一步，如何处理 $T^{n-1}$ ？

　　n 很大很大很大；

　　考虑到秦九韶算法，将 n 分解；

　　假设 n-1 = 3194;

　　那么 n 可分解为 $n=\bigg(\Big(\big((3\times 10)+1\big)\times 10+9\Big)\times 10+4\bigg)$;

　　在计算 $T^{3194}$ 时，可以按照字符串的位数进行处理；

　　先计算 ans = T³;

　　ans = ans¹⁰·T¹;(ans=T³¹)

　　ans = ans¹⁰·T⁹;(ans = T³¹⁹)

　　ans = ans¹⁰·T⁴;(ans = T³¹⁹⁴)

•Code

1 #include
       
         2 using namespace std; 3 #define mem(a,b) memset(a,b,sizeof(a)) 4 #define ll long long 5 const int N=5; 6 const int maxn=1e6+50; 7  8 int f[2]; 9 int a,b,mod;10 char s[maxn];11 struct Matrix12 {13     ll A[N][N];14 15     Matrix()16     {17         mem(A,0);18     }19     void Init()20     {21         for(int i=0;i < N;++i)22             A[i][i]=1;///构造单位阵23     }24 }t,ans;25 26 Matrix mult(Matrix a,Matrix b)///a*b27 {28     Matrix tmp;29     for(int i=1;i <= 2;++i)30         for(int j=1;j <= 2;++j)31             for(int k=1;k <= 2;++k)32             {33                 tmp.A[i][j] += a.A[i][k]*b.A[k][j]%mod;34                 tmp.A[i][j] %= mod;35             }36     return tmp;37 }38 Matrix qPow(Matrix a,int b)///a^b39 {40     Matrix tmp;41     tmp.Init();42 43     while(b)44     {45         if(b&1)46             tmp=mult(tmp,a);47         a=mult(a,a);48         b >>= 1;49     }50     return tmp;51 }52 int Solve()53 {54     ans.Init();55     t.A[1][1]=a;56     t.A[1][2]=b;57     t.A[2][1]=1;58 59     int len=strlen(s+1);60     for(int i=len;;--i)61     {62         if(s[i] != '0')63         {64             s[i]--;65             for(int j=i+1;j <= len;++j)66                 s[j]='9';67             break;68         }69     }70 71     for(int i=1;i <= len;++i)72     {73         ans=qPow(ans,10);///ans^1074         ans=mult(ans,qPow(t,s[i]-'0'));///ans*t^(s[i]-'0')75     }76     return (ans.A[1][1]*f[1]%mod+ans.A[1][2]*f[0]%mod)%mod;77 }78 int main()79 {80     scanf("%d%d",f+0,f+1);81     scanf("%d%d",&a,&b);82     scanf("%s",s+1);83     scanf("%d",&mod);84 85     printf("%d\n",Solve());86 87     return 0;88 }
       

 

 

---

G.subsequence(DP)

•题意

　　给你两个只包含字符 '0'~'9' ，长度分别为 n,m 的字符串 s,t；

　　求 s 的子序列 s' 的个数，满足 s' > t;

•题解

　　定义 dp[ i ][ j ] 表示 s 的前 i 个字符组成的子序列 > t₁t₂t₃...t_j 的子序列的总个数；

　　首先，预处理出 dp[ i ][ 1 ];

　　该如何处理呢？

　　dp[ i ][ 1 ] = 2ⁱ - 1 - illegal;

　　illegal 指的是不合法的子序列个数，即 s 的前 i 个字符组成的所有的子序列中 < t₁ 的子序列个数；

　　不合法的子序列主要包含两类：1.存在 s_i ≤ t₁ , 2.以0开头的子序列；

　　预处理出 dp[ i ][ 1 ] 后，接下来就是状态转移了；

　　　　dp[ i ][ j ] = dp[ i-1][ j ] + dp[ i-1][ j-1];

　　如果由 s 的前 i-1 个字符组成的子序列 s' 都满足 s' >  t₁t₂...t_j 的话，那么肯定有 s's_i > t₁t₂...t_j ；

　　如果由 s 的前 i-1 个字符组成的子序列 s' 都满足 s' >  t₁t₂...t_j-1 的话，那么肯定有 s's_i > t₁t₂...t_j-1t_j ；

　　当然，如果 s_i ≤ t_j ，上述两种情况便是 dp[ i ][ j ] 的全部情况；

　　如果 s_i > t_j 呢？

　　那是不是就漏掉了“由 s 的前 i-1 个字符组成的子序列 s' 满足 s' ==  t₁t₂...t_j”这种情况了？

　　这种情况该如何处理呢？

　　定义 $f_{i,j}$ 表示由s的前 i 位组成的子序列==t₁t₂...t_j 组成的子序列的总个数；

　　提前预处理出 $f_{i,j}$；

　　然后，在处理 s_i > t_j 的情况的时候，令 dp[ i ][ j ] 额外加上 f[ i-1][ j-1] 就好了；

•Code

1 #include
       
          2 using namespace std;  3 #define ll long long  4 #define mem(a,b) memset(a,b,sizeof(a))  5 const int MOD=998244353;  6 const int maxn=3e3+50;  7   8 int n,m;  9 char s[maxn]; 10 char t[maxn]; 11 ll dp[maxn][maxn];///dp[i][j]:由s的前i位组成的子序列>t1,t2,...,tj组成的子序列的总个数 12 ll f[maxn][maxn];///f[i][j]:由s的前i位组成的子序列==t1,t2,...,tj组成的子序列的总个数 13 vector
        
         v; 14  15 ll qPow(ll a,ll b) 16 { 17     ll ans=1; 18     a %= MOD; 19  20     while(b) 21     { 22         if(b&1) 23             ans=ans*a%MOD; 24         a=a*a%MOD; 25         b >>= 1; 26     } 27     return ans; 28 } 29 void initf() 30 { 31     for(int i=1;i <= n;++i) 32     { 33         f[i][1]=f[i-1][1]; 34         if(s[i] == t[1]) 35             f[i][1]++; 36  37         f[i][1] %= MOD; 38     } 39     for(int j=2;j <= m;++j) 40     { 41         for(int i=1;i <= n;++i) 42         { 43             f[i][j]=f[i-1][j]; 44             if(s[i] == t[j]) 45                 f[i][j] += f[i-1][j-1]; 46  47             f[i][j] %= MOD; 48         } 49     } 50 } 51 void Initdp() 52 { 53     for(int i=1;i <= n;++i) 54         dp[i][1]=(qPow(2,i)-1+MOD)%MOD; 55  56     int cnt=0; 57     v.clear(); 58     for(int i=1;i <= n;++i) 59     { 60         if(s[i] == '0')///记录所有s[i]=='0'的位置 61             v.push_back(i); 62  63         if(s[i] <= t[1]) 64             cnt++; 65         dp[i][1] -= cnt;///去掉si <= t1 的个数 66         dp[i][1]=(dp[i][1]+MOD)%MOD; 67     } 68     for(int i=1;i <= n;++i)///去掉前导0的个数 69     { 70         for(int j=0;j < v.size();++j) 71         { 72             if(v[j] >= i) 73                 break; 74             dp[i][1]=(dp[i][1]-(qPow(2,i-v[j])-1)+MOD)%MOD; 75         } 76     } 77 } 78 ll Solve() 79 { 80     for(int i=0;i <= n;++i) 81         for(int j=0;j <= m;++j) 82             f[i][j]=dp[i][j]=0; 83  84     initf();///预处理f 85     Initdp();///预处理dp[i][1] 86  87     for(int i=2;i <= n;++i) 88     { 89         for(int j=2;j <= min(i,m);++j) 90         { 91             dp[i][j]=dp[i-1][j]+dp[i-1][j-1]; 92             if(s[i] > t[j]) 93                 dp[i][j] += f[i-1][j-1]; 94             dp[i][j] %= MOD; 95         } 96     } 97     return dp[n][m]%MOD; 98 } 99 int main()100 {101 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);102     int test;103     scanf("%d",&test);104     while(test--)105     {106         scanf("%d%d",&n,&m);107         scanf("%s%s",s+1,t+1);108 109         printf("%lld\n",Solve());110     }111     return 0;112 }
        
       

 

 

 

---

H.subsequence 2(拓扑序)

•题意

　　有一个长度为 n 的隐藏字符串 s；

　　s 中只包含小写英文字母的前 m 个字母；

　　现在给你 $\frac{m\times (m-1)}{2}$ 对关系，每对关系给你一个只包含两种字符串；

　　让你还原 s 使得其满足上述 $\frac{m\times (m-1)}{2}$ 对关系的相对位置；

　　如果不存在这样的 s，输出 -1；

•题解

　　

•Code

1 #include
       
          2 using namespace std;  3 #define mem(a,b) memset(a,b,sizeof(a))  4 const int maxn=1e4+50;  5   6 int n,m;  7 int cnt;  8 int a[30];  9 int in[maxn]; 10 char s[maxn]; 11 bool vis[30]; 12 vector
        
         p[30]; 13 map
         
          f; 14 int num; 15 int head[maxn]; 16 struct Edge 17 { 18     int to; 19     int next; 20 }G[maxn*10]; 21 void addEdge(int u,int v) 22 { 23     G[num]=Edge{v,head[u]}; 24     head[u]=num++; 25 } 26 vector
          
           ans; 27 bool vis2[maxn]; 28  29 void DFS(int u) 30 { 31     ans.push_back(u); 32     vis2[u]=true; 33  34     for(int i=head[u];~i;i=G[i].next) 35     { 36         int to=G[i].to; 37         if(!vis2[to]) 38             in[to]--; 39     } 40     for(int i=head[u];~i;i=G[i].next) 41     { 42         int to=G[i].to; 43         if(!vis2[to] && !in[to]) 44             DFS(to); 45     } 46 } 47 void Solve() 48 { 49     int x; 50     for(int i=1;i <= cnt;++i) 51         if(!in[i]) 52             x=i; 53  54     mem(vis2,false); 55     DFS(x); 56  57     if(ans.size() != n) 58     { 59         puts("-1"); 60         return ; 61     } 62      63     for(int i=0;i < ans.size();++i) 64         printf("%c",f[ans[i]]); 65     printf("\n"); 66 } 67 void Init() 68 { 69     num=0; 70     mem(head,-1); 71     mem(vis,false); 72     mem(in,0); 73 } 74 int main() 75 { 76 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin); 77     Init(); 78     scanf("%d%d",&n,&m); 79  80     cnt=0;///莫名bug，cnt定义成局部的就出错 81     for(int k=1;k <= m*(m-1)/2;++k) 82     { 83         char ch[2]; 84         int len; 85         scanf("%s%d",ch,&len); 86         if(len > 0) 87             scanf("%s",s+1); 88  89         for(int i=1;i <= len;++i) 90         { 91             int cur=s[i]-'a'; 92  93             if(vis[cur]) 94                 continue; 95  96             p[cur].push_back(++cnt); 97             f[cnt]=cur+'a'; 98         } 99 100         vis[ch[0]-'a']=true;101         vis[ch[1]-'a']=true;102 103         a[ch[0]-'a']=0;104         a[ch[1]-'a']=0;105 106         for(int i=1;i < len;++i)107         {108             int u=s[i]-'a';109             int v=s[i+1]-'a';110             111             a[u]++;112             addEdge(p[u][a[u]-1],p[v][a[v]]);113 114             in[p[v][a[v]]]++;115         }116     }117     Solve();118     return 0;119 }