codeforces 497E Subsequences Return

想法

做完这题，学了一些东西。

1、求一个串不同子序列个数的两种方法。解一 解二

2、这道题 \(n\) 很大，很容易想到矩阵加速，但是之前遇到的矩阵的题目，矩阵都是相同的，这题的矩阵虽然不同，但是至多 \(k\) 个，并且出现规律与 \(0\) ~ \(n-1\) 的 \(k\) 进制形态有关。题解中基于这点进行的优化和 \(dp\) 的思想又很像。

代码

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define rep(i, a, b) for(int i=(a); i<(b); i++)

#define sz(x) (int)x.size()

#define de(x) cout<< #x<<" = "<<x<<endl

#define dd(x) cout<< #x<<" = "<<x<<" "

typedef long long ll;

typedef pair<int, int> pii;

typedef vector<int> vi;

const int MOD=1e9+7, N=33;

ll n;

int k;

vi dig;

inline void upd(ll &a, ll b) {

	a+=b;

	if(a>=MOD) a-=MOD;

}

struct M {

	ll a[N][N];

	M() {memset(a,0,sizeof(a));}

	void Set() {rep(i,0,k+1) a[i][i]=1;}

	M operator * (const M &c) const {

		M res;

		rep(i,0,k+1) rep(j,0,k+1) rep(_,0,k+1) upd(res.a[i][j], a[i][_]*c.a[_][j]%MOD);

		return res;

	}

}A[N<<1][N], S[N<<1][N], P[N<<1][N], ans;

int main() {

	scanf("%lld%d",&n,&k);

	rep(i,0,k) {

		A[0][i].Set();

		rep(j,0,k+1) A[0][i].a[i][j]=1;

	}

	ll len=k;

	for(int i=1;len<=n;++i, len*=k) {

		S[i-1][k-1]=A[i-1][k-1];

		for(int j=k-2; ~j; --j) S[i-1][j]=A[i-1][j]*S[i-1][j+1];

		P[i-1][0]=A[i-1][0];

		rep(j,1,k) P[i-1][j]=P[i-1][j-1]*A[i-1][j];

		A[i][0]=S[i-1][0];

		rep(j,1,k) A[i][j]=S[i-1][j]*P[i-1][j-1];

	}

	while(n) {

		dig.pb(n%k);

		n/=k;

	}

	int s=0;

	ans.Set();

	for(int i=sz(dig)-1;~i;--i) {

		rep(j,0,dig[i]) {

			ans=ans*A[i][(j+s)%k];

		}

		s=(s+dig[i])%k;

	}

	ll res=1;

	rep(i,0,k) upd(res, ans.a[i][k]);

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

	return 0;

}