苍穹一粟
(Data Structure)
1
我的式子：
\begin{bmatrix}
1&0&0&0&0&0&0&\cdots&0&0\\
1&1&0&0&0&0&0&\cdots&0&0\\
1&2&1&0&0&0&0&\cdots&0&0\\
0&0&0&0&1&0&0&\cdots&0&0\\
0&0&0&0&0&1&0&\cdots&0&0\\
&&&&&\vdots\\
0&0&0&0&0&0&0&\cdots&0&1\\
p&q&r&c_{n}&c_{n-1}&c_{n-2}&c_{n-3}&\cdots&c_{2}&c_{1}
\end{bmatrix}
\times
\begin{bmatrix}
1\\
i\\
i^2\\
a_{i-n}\\
a_{i-n+1}\\
\cdots\\
a_{i-2}\\
a_{i-1}\\
\end{bmatrix}
=
\begin{bmatrix}
1\\
i+1\\
(i+1)^2\\
a_{i-n+1}\\
a_{i-n+2}\\
\cdots\\
a_{i-1}\\
a_{i}\\
\end{bmatrix}
代码：
#include <bits/stdc++.h>
// #define int long long
using lint = long long;
const int N = 50;
const int MOD = 1e9 + 7;
template<typename T> // T 表示矩阵存的值的类型
struct Matrix {
size_t n, m; // n 为行数，m 为列数
std::vector<std::vector<T>> a;
Matrix(size_t _n = 0, size_t _m = 0) : n(_n), m(_m) {
a.resize(_n);
for (size_t i = 0; i < _n; ++i)
a[i].resize(_m);
}
Matrix(const std::vector<std::vector<T>> &_a) : n(_a.size()), m(_a[0].size()), a(_a) {}
void build() { for (size_t i = 0; i < n; ++i) a[i][i] = 1; }
void resize(size_t _n = 0, size_t _m = 0) {
n = _n, m = _m;
a = std::vector<std::vector<T>>(n, std::vector<T>(m));
}
Matrix<T> operator*(const Matrix<T> &A) {
if (m != A.n) throw "Error";
Matrix<T> res(n, A.m);
for (size_t i = 0; i < n; ++i) // 枚举最终矩阵的行
for (size_t j = 0; j < A.m; ++j) // 枚举最终矩阵的列
for (size_t k = 0; k < m; ++k) // 枚举 A 的列（B 的行）
(res.a[i][j] += a[i][k] * A.a[k][j] % MOD) %= MOD; // 实际实现中可能需要取模
return res;
}
void operator*=(const Matrix<T> &A) {
*this = *this * A;
}
};
template <typename T>
std::istream &operator>>(std::istream &is, Matrix<T> &A) { // 读入矩阵
for (size_t i = 0; i < A.n; ++i)
for (size_t j = 0; j < A.m; ++j)
is >> A.a[i][j];
return is;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const Matrix<T> &A) { // 输出矩阵
for (size_t i = 0; i < A.n; ++i) {
for (size_t j = 0; j < A.m; ++j)
os << A.a[i][j] << ' ';
os << '\n';
}
return os;
}
template <typename T>
Matrix<T> qpow(Matrix<T> &P, size_t b) { // 矩阵快速幂
Matrix<T> ans(P.a.size(), P.a.size());
ans.build();
for (; b; b >>= 1) {
if (b & 1) ans *= P;
P *= P;
}
return ans;
}
int n, p, q, r, c[N];
long long k;
Matrix<lint> S, T, ans;
void init_S() {
S.resize(n + 3, 1);
S.a[0][0] = 1, S.a[1][0] = n, S.a[2][0] = n * n;
for (int i = 3; i < n + 3; ++i)
std::cin >> S.a[i][0];
}
void init_T() {
T.resize(n + 3, n + 3);
T.a[0][0] = T.a[1][0] = T.a[1][1] = T.a[2][0] = T.a[2][2] = 1;
T.a[2][1] = 2;
for (int i = 3; i < n + 2; ++i) T.a[i][i + 1] = 1;
for (int i = 1; i <= n; ++i) std::cin >> c[i];
std::cin >> p >> q >> r;
T.a[n + 2][0] = p, T.a[n + 2][1] = q, T.a[n + 2][2] = r;
for (int i = 1; i <= n; ++i)
T.a[n + 2][i + 2] = c[n - i + 1];
}
signed main() {
std::cin >> n >> k;
init_S(), init_T();
if (k < n)
return std::cout << S.a[k + 3][0] << '\n', 0;
auto ans = qpow(T, k - n + 1) * S;
std::cout << ans.a[n + 2][0] << '\n';
return 0;
}
目前信友队 AC，但是 CF 上 WA on 23，提交记录。
求助洛谷可以给关注
2 个赞
刘恩印
(刘恩印)
2
同问，WA #23
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N=1e2+5,M=1e9+7;
struct matrix{
int sizeh,sizel;//几行几列
ll val[N][N];
matrix(){
sizeh=0,sizel=0;
memset(val,0,sizeof val);
}
matrix(int X){
//单位方阵
sizeh=sizel=X;
for(int i=1;i<=X;i++){
for(int j=1;j<=X;j++){
if(i==j)val[i][j]=1;
else val[i][j]=0;
}
}
}
matrix operator*(const matrix &A)const{
matrix ret;
ret.sizeh=this->sizeh;
ret.sizel=A.sizel;
for(int i=1;i<=this->sizeh;i++){
for(int j=1;j<=A.sizel;j++){
//枚举ret[i][j]
for(int k=1;k<=this->sizel;k++){
ret.val[i][j]+=(this->val[i][k]*A.val[k][j])%M;
ret.val[i][j]%=M;
}
}
}
return ret;
}
};
matrix fs,xs;
matrix qpow(matrix A,ll k){
matrix ret(A.sizeh);
while(k){
if(k&1){
ret=ret*A;
}
A=A*A;
k>>=1;
}
return ret;
}
int n,k,p,q,r;
signed main(){
cin>>n>>k;
fs.sizel=n+3,fs.sizeh=1;
for(int i=0;i<n;i++)cin>>fs.val[1][i+1];
xs.sizeh=n+3,xs.sizel=n+3;
for(int i=0;i<n;i++)cin>>xs.val[n-i][n];
cin>>p>>q>>r;
if(k<n){
cout<<fs.val[1][k]<<endl;
return 0;
}
for(int i=2;i<=n;i++)xs.val[i][i-1]=1;
xs.val[n+1][n+1]=1;
xs.val[n+2][n+2]=1;
xs.val[n+1][n+2]=1;
xs.val[n+3][n+3]=1;
xs.val[n+2][n+3]=2;
xs.val[n+1][n+3]=1;
xs.val[n+1][n]=p;
xs.val[n+2][n]=q;
xs.val[n+3][n]=r;
fs.val[1][n+1]=1;
fs.val[1][n+2]=n;
fs.val[1][n+3]=n*n;
// for(int i=1;i<=n+3;i++){
// for(int j=1;j<=n+3;j++){
// cerr<<xs.val[i][j]<<" ";
// }
// cerr<<endl;
// }
xs=qpow(xs,k-n+1);
// for(int i=1;i<=n+3;i++){
// for(int j=1;j<=n+3;j++){
// cerr<<xs.val[i][j]<<" ";
// }
// cerr<<endl;
// }
fs=fs*xs;
cout<<fs.val[1][n];
return 0;
}
1 个赞
苍穹一粟
(Data Structure)
6
@崩坏星穹铁道 抱歉，这个提交记录看不见，我也看不见数据。。。能帮忙调一下吗，谢谢！
1 个赞
徐昊轩
(徐昊轩)
8
思路是对的啊，你可以康我的代码比较一下
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=20;
int n,k,p,q,r,a[N],c[N];
struct mat{
int n,m,a[N][N];
mat(){
memset(a,0,sizeof(a));
n=0;
m=0;
}
void print(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
};
mat I,M,ans;
mat operator * (const mat &a,const mat &b){
mat c;
c.n=a.n;
c.m=b.m;
for(int i=1;i<=a.n;i++){
for(int j=1;j<=b.m;j++){
for(int k=1;k<=a.m;k++){
c.a[i][j]=(c.a[i][j]+(a.a[i][k]*b.a[k][j])%mod)%mod;
}
}
}
return c;
}
mat qpow(mat a,int b){
mat ans=I;
while(b){
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
void init(){
I.n=I.m=n+3;
M.n=M.m=n+3;
ans.n=n+3;
ans.m=1;
for(int i=1;i<=I.n;i++){
I.a[i][i]=1;
}
for(int i=1;i<=n;i++){
M.a[1][i]=c[i];
}
for(int i=2;i<=n;i++){
M.a[i][i-1]=1;
}
M.a[1][n+1]=p;
M.a[1][n+2]=q;
M.a[1][n+3]=r;
M.a[n+1][n+1]=1;
M.a[n+2][n+1]=1;
M.a[n+2][n+2]=1;
M.a[n+3][n+1]=1;
M.a[n+3][n+2]=2;
M.a[n+3][n+3]=1;
for(int i=1;i<=n;i++){
ans.a[i][1]=a[n-i];
}
ans.a[n+1][1]=1;
ans.a[n+2][1]=n;
ans.a[n+3][1]=n*n;
}
signed main(){
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
a[i]%=mod;
}
for(int i=1;i<=n;i++){
cin>>c[i];
}
cin>>p>>q>>r;
if(k<n) cout<<a[k-1]%mod<<endl;
init();
ans=qpow(M,k-n+1)*ans;
cout<<ans.a[1][1]<<endl;
}
1 个赞
苍穹一粟
(Data Structure)
10
全开是过了，没用
有没有一种可能，你的在 CF 上也过不去（bushi
1 个赞
