day9

正睿提高

T1

一共有$n$个人参加了考试。
无聊的助教决定不告诉大家每个人的名次，而是让大家自己猜。
首先，大家知道了第$i$个人的名次区间是$[L_i,R_i]$。
除此之外，又有$m$条其他信息，形如$u_i,v_i$，表示第$u_i$个人考的要比$v_i$好（即排名更低）。
现在，小S想要知道，是否有一个合法的排名，满足上述所有的要求。如果有，请输出任意一组解（输出第i名的id），否则输出"-1"（不含括号）。

分析：
题目其实有两个限制：排名在[L,R]之间，u的排名小于v的排名。
对于第二个相当于是一张图，拓扑排序一下。（首先判断不能有环）。
利用拓扑序将[L,R]的限制收紧，u->v，R[u]=min(R[u],R[v]-1])。然后此时就消去了第二个限制。
考虑第一个限制：肯定是贪心的选。那么如何贪心？
从第一个开始枚举第i名的是谁，然后将L在i之前的都加入到一个队列里，（就是说这些点可能在第i个位置，毕竟L<=i了），然后从这些点中选一个右端点最小的，让它在第i个点就行了。
这里加入小于等于i的点的时候，不能直接暴力用vector直接记录下所有左端点在i的。因为即使是R[i]拓扑后，前一个的R一定小于等于下一个的R，但是L的限没有去掉。如果存在这样的情况，1->2，L[1]=6,R[1]=7,L[2]=1,R[2]=8，那么开始就把第二个点加入了一号位置，但是此时1号点还没有放，所以应该按照拓扑序为第一关键字，L为第二关键字，加点。

#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;
char buf[100000],*_p1 = buf,*_p2 = buf;
#define nc() (_p1==_p2&&(_p2=(_p1=buf)+fread(buf,1,100000,stdin),_p1==_p2) ? EOF :*_p1++) 
inline int read() {
    int x=0,f=1;char ch=nc();for(;!isdigit(ch);ch=nc())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=nc())x=x*10+ch-'0';return x*f;
}
#define pa pair<int,int>
#define mp make_pair
const int N = 300005;
struct Edge{
    int to, nxt;
}e[1000005];
int head[N], En;
int deg[N], deg2[N], L[N], R[N], q[N], ans[N];
int n, m;
priority_queue< pa, vector< pa >, greater< pa > > q1, q2;
void add_edge(int u,int v) {
    ++En; e[En].to = v; e[En].nxt = head[u]; head[u] = En;
    deg[v] ++, deg2[v] ++;
}
bool solve() {
    int H = 1, T = 0;
    for (int i = 1; i <= n; ++i) if (!deg2[i]) q[++T] = i; 
    while (H <= T) {
        int u = q[H ++];
        for (int i = head[u]; i; i = e[i].nxt) 
            if (!(--deg2[e[i].to])) q[++T] = e[i].to;
    }
    if (T < n) return 0; //因为有环所以没有遍历完所有的点
    for (int i = n; i >= 1; --i) {
        int u = q[i];
        for (int i = head[u]; i; i = e[i].nxt) 
            R[u] = min(R[u], R[e[i].to] - 1);
        if (L[u] > R[u]) return 0;
    }
    for (int i = 1; i <= n; ++i) if (!deg[i]) q1.push(mp(L[i], i));
    for (int now = 1; now <= n; ++now) {
        while (!q1.empty() && q1.top().first <= now) 
            q2.push(mp(R[q1.top().second], q1.top().second)), q1.pop();
        if (q2.empty()) return 0;
        int u = q2.top().second; q2.pop();
        ans[now] = u;
        if (R[u] < now) return 0;
        for (int i = head[u]; i; i = e[i].nxt) {
            if (!(--deg[e[i].to])) q1.push(mp(L[e[i].to], e[i].to));
        }
    }
    for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]); 
    return 1;
}
int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) L[i] = read(), R[i] = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(); 
        add_edge(u, v);
    }
    if (!solve()) puts("-1");
    return 0;
}

T2

小S决定送给小萌一个礼物。
这是一个特殊的礼物，它是一个集合，且集合所有的数的$\gcd$为$1$，所有数的$\text{lcm}$为$m$。
小S他有多少种不同的送礼方案呢。两个送礼方案不同当且仅当存在某个$x$在一个方案中而不在另一个中。
答案对$998244353$取模。

#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;
int p[N], cnt;
LL Ans;
void init(LL m) {
    for (int i = 2; 1ll * i * i <= m; ++i) {
        if (m % i) continue;
        cnt ++;
        while (m % i == 0) p[cnt] ++, m /= i;
    }
    if (m > 1) p[++cnt] = 1;
}
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;
}
void dfs(int x,int c,int val) {
    if (x > cnt) {
        Ans += 1ll * (ksm(2, val) - 1 + mod) * c % mod;
        if (Ans >= mod) Ans -= mod;
        return ;
    }
    dfs(x + 1, c, 1ll * val * (p[x] + 1) % (mod - 1));
    dfs(x + 1, (-2ll * c % mod + mod) % mod, 1ll * val * p[x] % (mod - 1));
    if (p[x] > 1) dfs(x + 1, c, 1ll * val * (p[x] - 1) % (mod - 1));
}
int main() {
    LL m; cin >> m;
    init(m);
    dfs(1, 1, 1);
    cout << Ans;
    return 0;
}