Codeforces 1009e Intercity Travelling

Codeforces 1009e Intercity Travelling"/>

Codeforces 1009e Intercity Travelling

把n从2到5的情况都列出来会发现n每次加1 就只是在最高位加一个数字

n=2 即1 3

n=3 即1 3 8

n=5 即1 3 8 20 48

规律就是cs[k]=cs[k-1]*3-(k-2)的前缀和

#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long int
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
const int inf = 0x3f3f3f3f;
long long mod = 998244353;	
long long cs[1111111];long long qz[1111111];
int main()
{cs[1] =qz[1]= 1;cs[2] = 3;cs[3] = 8;cs[4] = 20;qz[2] = 4;qz[3] = 12;qz[4] = 32;for (int i = 5; i <= 1000000; i++){cs[i] = (cs[i - 1]*3+ mod  - qz[i - 2]) % mod;qz[i] = (qz[i - 1] + cs[i]) % mod;}int n;while (cin >> n ){long long ans = 0;long long a;for (int i = n; i >= 1; i--){scanf("%lld", &a);ans =(ans+ (a*cs[i] % mod)) % mod;}cout << ans << endl;}return 0;
}