day9

正睿停课

真的是啥都不会啊。。。
居然啥都想不出，还码不出。。。

T1

题目链接
https://www.zhihu.com/question/36252015/answer/66946594

填完1后的方案，剩下的填法都是一样的。
所以，求出合法的填1的方案 / 总的填1的方案 * 数独的总的方案。就是答案。
求合法的1的方案。
1、状压：
f[i][sta]记录到第i行，那些列位置没有填。可以三行三行的转移，所以i只有012就行了。前三行的状态一定是001|010|100类似的，就是每三位一个1。然后枚举下一个三行的哪些列是1。发现f[0/1/2]的合法的状态互不干扰（即f[0]只有每三位内一个1，f[1]只有每三位内2个1，f[2]只有每三位内3个1的方案是合法的），于是可以压掉一维。
2、搜索：
记录每个块内有没有，这一列有没有。每一行一行的转移，由于去掉很多状态，复杂度还是挺小的。
总的填1的方案数：求一下全0的数独。
数独的总方案数：用样例解一下？百度？

输入：
1
101101010
010000100
100100100
001001000
111011100
100100100
111010100
010101011
101101010
输出：
915672442

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 20;
const int mod = 998244353;
char a[N][N];
int vis[N], B[N];
int sta1 = 46656, ista1 = 549081465, tot = 719935075, Ans;
int ksm(int a,int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}
int getblock(int x,int y) {
    if (x <= 3) {
        return (y - 1) / 3 + 1;
    }
    if (x >= 4 && x <= 6) {
        return 3 + (y - 1) / 3 + 1;
    }
    return 6 + (y - 1) / 3 + 1;
}
void dfs(int x) {
    if (x == 10) { Ans ++; return ; }
    for (int i = 1; i <= 9; ++i) {
        if (a[x][i] == '1') continue;
        if (vis[i]) continue;
        int k = getblock(x, i);
        if (B[k]) continue;
        vis[i] = B[k] = true;
        dfs(x + 1);
        vis[i] = B[k] = false;
    }
}
void solve() {
    for (int i = 1; i <= 9; ++i) scanf("%s", a[i] + 1);
    Ans = 0;
    dfs(1);
    printf("%lld\n", 1ll * Ans * ista1 % mod * tot % mod);
}
int main() { 
//  191 / sta1 * tot = 915672442
//  int t1 = ksm(191, mod - 2);
//  cout << 1ll * 915672442 * t1 % mod * sta1 % mod; // tot
    for (int T = read(); T --; ) solve();
    return 0;
}

T2

题目链接
每个点当然还是越早到越好，即使到了等红绿灯。所以直接求一下最短路即可，过程中求出每条边的权值。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
#define pa pair<LL,int>
#define mp make_pair
const int N = 500005;
const LL INF = 1e18;
struct Edge{
    int to, w, k, l, r, nxt;
    Edge() { }
    Edge(int _to, int _w, int _k, int _l, int _r, int _nxt)  {
        to = _to, w = _w, k = _k, l = _l, r = _r, nxt = _nxt;
    }
}e[2000005];
int head[N], En, n;
LL dis[N];
bool vis[N];
priority_queue< pa > q;
LL Calc(int len, int now, int k, int l, int r) {
    LL ans = 0; int x = r - l + 1, y = k - x; // x走的时间，y等待的时间 
    if (now <= l) ans += l - now; // 先到达时刻L处 
    else if (now > l && now <= r) {
        if (r - now + 1 >= len) return len;
        ans += r - now + 1 + y; len -= r - now + 1;
    }
    else if (now > r) ans += k - now + l; // k - r + l！！！ 
    ans += len; // 一定要走的 
    ans += y * ((len - 1) / x); // 等待的时间 
    return ans; 
}
void Dijkstra() {
    for (int i = 1; i <= n; ++i) 
        vis[i] = false, dis[i] = INF;
    dis[1] = 0;
    q.push(mp(0, 1));
    while (!q.empty()) {
        pa now = q.top(); q.pop();
        int u = now.second;
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            LL w = Calc(e[i].w, dis[u] % e[i].k, e[i].k, e[i].l, e[i].r);
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(mp(-dis[v], v));
            }
        }
    }
    for (int i = 1; i <= n; ++i) 
        printf("%lld\n", dis[i]);
}
int main() {    
    n = read();int m = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read(), k = read(), l = read(), r = read();
        ++En; e[En] = Edge(v, w, k, l, r, head[u]); head[u] = En;
        ++En; e[En] = Edge(u, w, k, l, r, head[v]); head[v] = En;
    }
    Dijkstra();
    return 0;
}
//LL Calc(int len, int now, int k, int l, int r) {
//  LL ans=0;
//  if (now <= r && now >= l) {
//      if (r - now + 1 >= len) return len;
//      ans += r - now + 1; len -= r - now + 1; now = r + 1;
//  }
//  if (now > r) ans += k - now;
//  else ans -= now;
//  
//  int x = r - l + 1;
//  ans += 1ll * (len - 1) / x * k;
//  len = (len - 1) % x + 1;
//  ans += l + len;
//  return ans;
//}