本文主要是介绍Codeforces 1009e Intercity Travelling，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://codeforces.com/problemset/problem/1009/E
把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;
}
这篇关于Codeforces 1009e Intercity Travelling的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
