【51nod】2590 持續討伐

掙扎著卡了卡常過了

記\(dp[i][j]\)為到第\(i\)位，和第\(i\)位相連的部分長度\(x^{j}\)乘上之前部分所有方案\(x^{K}\)總和

轉移用二項式定理展開即可，若這位不選，可以有\(dp[i + 1][j] = dp[i][K]\)

矩陣乘法優化一下，卡常用預處理出2的幾次冪的矩陣的答案

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define eps 1e-10 #define ba 47 #define MAXN 2005 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template<class T> void read(T &res) {res = 0;T f = 1;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 +c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) {x = -x;putchar('-');}if(x >= 10) {out(x / 10);}putchar('0' + x % 10); } const int MOD = 998244353; int N,M,K; int C[15][15]; bool vis[55]; int inc(int a,int b) {return a + b >= MOD ? a + b - MOD : a + b; } int mul(int a,int b) {return 1LL * a * b % MOD; } void update(int &x,int y) {x = inc(x,y); } struct Matrix {int f[9][9];Matrix() {memset(f,0,sizeof(f));}friend Matrix operator * (const Matrix &a,const Matrix &b) {Matrix c;for(int i = 0 ; i <= K ; ++i) {for(int j = 0 ; j <= K ; ++j) {for(int h = 0 ; h <= K ; ++h) {update(c.f[i][j],mul(a.f[i][h],b.f[h][j]));}}}return c;}void unit() {for(int i = 0 ; i <= K ; ++i) f[i][i] = 1;}friend Matrix fpow(Matrix a,int c) {Matrix res,t = a;res.unit();while(c) {if(c & 1) res = res * t;t = t * t;c >>= 1;}return res;} }A,B,ans,P[35]; void Solve() {read(N);read(M);read(K);for(int i = 0 ; i <= K ; ++i) {C[i][0] = 1;for(int j = 1 ; j <= i ; ++j) {C[i][j] = inc(C[i - 1][j - 1],C[i - 1][j]);}}for(int i = 0 ; i <= K ; ++i) {for(int j = 0 ; j <= i ; ++j) {update(A.f[j][i],C[i][j]);}}B = A;for(int i = 0 ; i <= K ; ++i) update(B.f[K][i],1);P[0] = B;for(int i = 1 ; i <= 30 ; ++i) P[i] = P[i - 1] * P[i - 1];int p = 1,t;ans.unit();for(int i = 1 ; i <= M ; ++i) {read(t);for(int j = 0 ; j <= 29 ; ++j) {if((t - p) >> j & 1) ans = ans * P[j];}p = t;ans = ans * A;++p;}if(p != N) {for(int j = 0 ; j <= 29 ; ++j) {if((N - p) >> j & 1) ans = ans * P[j];}}int res = 0;for(int i = 0 ; i <= K ; ++i) {update(res,ans.f[i][K]);}out(res);enter; } int main(){ #ifdef ivorysifreopen("f1.in","r",stdin); #endifSolve();return 0; }

轉載于:https://www.cnblogs.com/ivorysi/p/11050912.html

總結

以上是生活随笔為你收集整理的【51nod】2590 持续讨伐的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。