2021GDCPC Guangdong University Student Programming Competition H.History

题意：
给定一个由n个点,m条边组成的图,每走一步,All edge weights are transformed according to the following formula

求1到n的最短路

思路：
If it is transformed into different each time,namoThis question doesn't feel feasible,But it was found after several consecutive substitutions,This is a period of4的循环,So it can be done with a layered graph

We can start by building a four-layer map,It can also exist side by sidedijFind the distance between different layers within the function,Here I use the second method

Code:

#include <bits/stdc++.h>
// #define debug freopen("_in.txt", "r", stdin);
#define debug freopen("_in.txt", "r", stdin), freopen("_out.txt", "w", stdout);
typedef long long ll;
typedef unsigned long long ull;
typedef struct Node *bintree;
using namespace std;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll maxn = 1e7 + 10;
const ll maxm = 2e6 + 10;
const ll mod = 998244353;
const double pi = acos(-1);
const double eps = 1e-8;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

ll T, n, m, q, d, kase = 0;
priority_queue<pair<ll, ll>> que;
ll arr[100];
ll dp[3][maxn];

void solve()
{
    
    scanf("%lld", &n);
    printf("%lld\n",(dp[0][n]+dp[1][n])%mod);
}

signed main()
{
    
    // debug;
    scanf("%lld", &T);
    // T = 1;
    arr[1] = arr[2] = 1;
    for (ll i = 2; i <= 50; i++)
    {
    
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    dp[0][0] = 1;
    dp[0][1] = 1;
    dp[1][1] = 1;
    ll now = 0;
    for (ll i = 2; i <= 1e7; i++)
    {
    
        if (i >= arr[now])
        {
    
            while (i >= arr[now])
            {
    
                now++;
            }
            now--;
        }
        ll v1=arr[now],v2=arr[now-1];
        dp[0][i]=(dp[0][i-v1]+dp[1][i-v1])*v1;
        dp[0][i]%=mod;
        if(i-v2<v2)
        {
    
            dp[1][i]=(dp[0][i-v2]+dp[1][i-v2])*v2;
        }
        else
        {
    
            dp[1][i]=(dp[1][i-v2])*v2;
        }
        dp[1][i]%=mod;
    }
    while (T--)
    {
    
        solve();
    }
}