WXH的路径

WXH的路径

思路：
走到每一步有许多选择，每种选择划出了一个区间，判断k在那个区间内，模拟向前走

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#define LL long long
#define N 1000010
#define mod 1000000000000000007LL
#define pr pair<char, int>
using namespace std;

LL x, y, k, cnt=0, f[N], vis[N], n, m, nxt[N];
char s[N], pos[N];
priority_queue < pr, vector<pr>, greater<pr> > q;

inline LL up( LL a, LL b ) {//没有模数只有边界的做法 
    LL c = a + b;
    if( c > mod ) c = mod;
    return c;
}

inline LL chen( LL a, LL b ) {//判位数 
    if((int)log((double)a) + (int)log((double)b) > (int)log((double)mod)) return mod;
    return a * b;
}

void init(){//预处理方案数 
    for(int i=n; i>=1; i--){
        for(int j=m; j>=1; j--){
            if(i==n && j==m) f[(i-1)*m+j] = 1;
            else {
                if(j != m) f[(i-1)*m+j] = f[(i-1)*m+j+1];
                if(i != n) f[(i-1)*m+j] = up(f[i*m+j], f[(i-1)*m+j]);
            }
        }
    }
}

inline void add(int x, LL tim){
    if((x - 1) / m < n - 1 && !vis[x + m])  q.push( make_pair(pos[x + m], x + m) );
    vis[x + m] = up(vis[x + m], tim);
    if(x - (x - 1) / m * m < m && !vis[x + 1])  q.push( make_pair(pos[x + 1], x + 1) );
    vis[x + 1] = up(vis[x + 1], tim);
}

int main(){
    freopen ("path.in", "r", stdin);
    freopen ("path.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    init();
    for(int i=1; i<=n; i++){
        scanf("%s", s+1);
        for(int j=1; j<=m; j++){
            pos[(i-1)*m+j] = s[j];
        }
    }
    cin >> k;
    q.push( make_pair(pos[1], 1) );
    vis[1] = 1;
    LL sum = 0, psum = 0; int pre = 0, now; char ch;
    if ( f[1] < k ){
        printf("Impossible\n");
        return 0;
    }
    while ( !q.empty() ){
        now = q.top().second;
        nxt[now] = pre; ch = pos[now];
        sum = up( sum, chen(f[now], vis[now]) );
        q.pop();
        pre = now;
        if(!q.empty() && q.top().first == ch) continue;
        if(sum >= k){
            while ( !q.empty() ) q.pop();
            add(now, vis[now]);
            while ( pos[nxt[now]] == ch ) { 
                now = nxt[now]; 
                add(now, vis[now]);
            }
            k -= psum;
            printf("%c", ch); cnt++;
            sum = 0; pre = 0;
            psum = 0;
        }
        else psum = sum;
    }
}