2021GDCPC广东省大学生程序设计竞赛 H.History

题意：
给定一个由n个点，m条边组成的图，每走一步，所有边权都会按以下公式变换

求1到n的最短路

思路：
如果每次都变换成不同的，namo这题感觉不太可做，但连续代入几次后发现，这是个周期为4的循环，故可以用分层图做

我们可以一开始建好四层图，也可以先存边在dij函数内求不同层之间的距离，这里我用了第二种方法

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();
    }
}