感觉...昨天是真的傻...
题意
T个询问，每个询问给一个n，求
$ \frac{\sum_{n}^{i = 1}Fib_{i} * i}{n * (n + 1) / 2} $
Fib是斐波那契数列，对998244353取模
然后...我昨天把n乘了之后就忘记取模了...
30分做法
设$ a_{i} = i * Fib_{i} $, 有$ a_{i} = a_{i - 1} + a_{i - 2} + Fib_{i - 1} + Fib_{i - 2} $，然后就写了一个5*5的转移矩阵，感觉很稳……
长这样：
\begin{bmatrix}
Fib_{i} & Fib{i - 1} & a_{i} & a_{i - 1} & sum_{i - 1}
\end{bmatrix}
转移矩阵长这样：
\begin{bmatrix}
1 & 1 & 1 & 0 & 0 \\
1 & 0 & 2 & 0 & 0\\
0 & 0 & 1 & 1 & 1\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1
\end{bmatrix}
虽然这个东西也过了几万组对拍，但是我喜闻乐见地把std也顺便写挂了（捂脸），所以这两个东西都只有10分...
Code：
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll; const ll mod = ; int testCase;
ll n; struct Matrix {
ll l1, l2, s[][]; inline void init() {
l1 = l2 = ;
memset(s, , sizeof(s));
} friend Matrix operator * (const Matrix a, const Matrix b) {
Matrix res;
res.init();
res.l1 = a.l1, res.l2 = b.l2;
for(int i = ; i < a.l1; i++)
for(int j = ; j < b.l2; j++)
for(int k = ; k < a.l2; k++)
res.s[i][j] = (res.s[i][j] + a.s[i][k] * b.s[k][j] % mod) % mod;
return res;
} inline Matrix pow(Matrix a, ll b) {
Matrix res = *this;
for(; b > ; b >>= ) {
if(b & ) res = res * a;
a = a * a;
}
return res;
} inline void print() {
for(int i = ; i < l1; i++, printf("\n"))
for(int j = ; j < l2; j++)
printf("%lld ", s[i][j]);
} } f; inline ll pow(ll x, ll y) {
ll res = ;
for(x %= mod; y > ; y >>= ) {
if(y & ) res = res * x % mod;
x = x * x % mod;
}
return res;
} inline ll solve() {
if(n == ) return 1LL;
if(n == ) return 3LL; Matrix g;
g.init();
g.l1 = , g.l2 = ;
g.s[][] = g.s[][] = g.s[][] = ;
g.s[][] = ;
g.s[][] = ;
// g.print(); g = g.pow(f, n - ); // g.print(); return g.s[][];
} int main() {
f.init();
f.l1 = f.l2 = ;
f.s[][] = f.s[][] = f.s[][] = ;
f.s[][] = f.s[][] = f.s[][] = f.s[][] = ;
f.s[][] = f.s[][] = ;//f.s[4][2] = 1;
f.s[][] = ; // f.print(); for(scanf("%d", &testCase); testCase--; ) {
scanf("%lld", &n);
ll tmp = n * (n + ) / ;
ll inv = pow(tmp, mod - );
ll sum = solve();
printf("%lld\n", inv * sum % mod);
}
return ;
}
100分做法
找规律题惹不起a...
$sum_{n} = n * Fib_{n + 2} - Fib_{n + 3} + 2$
所以就变成一个斐波那契了
并不能推导出来...
Code:
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll; const ll mod = ; int testCase;
ll n; struct Matrix {
ll s[][]; inline void init() {
memset(s, , sizeof(s));
} friend Matrix operator * (const Matrix a, const Matrix b) {
Matrix res;
res.init();
for(int i = ; i <= ; i++)
for(int j = ; j <= ; j++)
for(int k = ; k <= ; k++)
res.s[i][j] = (res.s[i][j] + a.s[i][k] * b.s[k][j] % mod) % mod;
return res;
} inline Matrix pow(ll b) {
Matrix res, a = *this;
res.init();
for(int i = ; i <= ; i++) res.s[i][i] = ;
for(; b > ; b >>= ) {
if(b & ) res = res * a;
a = a * a;
}
return res;
} } f; inline ll pow(ll a, ll b) {
ll res = ;
for(; b > ; b >>= ) {
if(b & ) res = res * a % mod;
a = a * a % mod;
}
return res;
} inline ll solve() {
Matrix res = f.pow(n + );
return (res.s[][] * n % mod - res.s[][] + + mod) % mod;
} int main() {
f.init();
f.s[][] = f.s[][] = f.s[][] = ;
for(scanf("%d", &testCase); testCase--; ) {
scanf("%lld", &n);
ll inv = pow((n * (n + ) / )% mod, mod - );
ll sum = solve();
// printf("%lld %lld\n", sum, inv);
printf("%lld\n", sum * inv % mod);
}
return ;
}
感觉还挺有趣的……