[題解]CLYZ2018省選訓(bao)練(zha)模拟賽 Day 10

一進制n次方程求解，世界性難題上場，瞬間全懵。

題目

T1：BZOJ 2734 / HNOI 2012 集合選數 (set)（狀壓DP）

T2：BZOJ 2302 / HAOI 2011 Problem c (c)（DP+組合數學）

T3：BZOJ 2742 / HEOI 2012 Akai的數學作業 (akai)（數學）

T1

分析

考慮構造出一個矩陣：

1248...361224...9183672...2754108216.................. 1 3 9 27 . . . 2 6 18 54 . . . 4 12 36 108 . . . 8 24 72 216 . . . . . . . . . . . . . . . . . .

即左上角的數為 1 1 ，此外每個數都等于它左邊的數乘33，上面的數乘 2 2 。

此問題就轉化成了在矩陣中取出一些元素，不能取相鄰元素的方案數。

由于矩陣的行數≤17≤17，列數 ≤11 ≤ 11 ，是以可以考慮狀态壓縮。

用 f[i][S] f [ i ] [ S ] 表示到了第 i i 行，此行的選取狀态為SS的方案數，就可以枚舉上一行的狀态進行轉移了。

同時注意， 這個矩陣并沒有涵蓋 1 1 到nn的所有數。是以要以每一個 既不是 2 2 的倍數又不是33的倍數的數作為矩陣的左上角進行DP，并将所有的結果相乘。

Source

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N =  + , MX =  + , M = , C = ( << ) + ;
int n, tot, cnt[N], ans = , num[M][M], f[M][C], aiv[C], T;
bool vis[N];
void DP(int x) {
    tot = ; int i, j, k, y, z; for (y = x; y <= n; y <<= ) {
        cnt[++tot] = ; for (z = y; z <= n; z *= )
            vis[num[tot][++cnt[tot]] = z] = ;
    }
    for (i = ; i <= T && aiv[i] < ( << cnt[]); i++) f[][i] = ;
    for (i = ; i <= tot; i++)
    for (j = ; j <= T && aiv[j] < ( << cnt[i]); j++) {
        int S = aiv[j]; f[i][j] = ;
        for (k = ; k <= T && aiv[k] < ( << cnt[i - ]); k++)
            if (!(S & aiv[k])) f[i][j] = (f[i][j] + f[i - ][k]) % MX;
    }
    int res = ; for (i = ; i <= T && aiv[i] < ( << cnt[tot]); i++)
        res = (res + f[tot][i]) % MX;
    ans = l * ans * res % MX;
}
int main() {
    int i, j; cin >> n; for (i = ; i < ( << ); i++) {
        bool tm = ; for (j = ; j < ; j++)
            if (((i >> j) & ) & ((i >> j - ) & )) tm = ;
        if (tm) aiv[++T] = i;
    }
    for (i = ; i <= n; i++)
        if (!vis[i]) DP(i); cout << ans << endl;
    return ;
}
           

T2

分析

轉換下定義：一種方案合法，等價于「編号 ≤i ≤ i 的人數至少 i i 個」。

證明：如果編号≤i≤i的人小于 i i 個，那麼編号大于ii的人數就大于 n−i n − i 個，但 i i 後面的座位隻有n−in−i個，超過 n−i n − i 個人擠在最後 n−i n − i 個座位顯然是不行的。

（下設 cnti c n t i 表示有 cnti c n t i 個人的編号已經被确定為 i i ，并且sumi=∑nj=icntjsumi=∑j=incntj）

判斷無解的情況：根據條件得到，如果存在一個 i i 使得n−m+∑ij=1cntjn−m+∑j=1icntj小于 i i ，那麼無解。

否則進行DP，定義狀态f[i][j]f[i][j]表示到了編号 i i ，編号≤i≤i的人數有 j j 個的方案數。邊界f[0][0]=1f[0][0]=1。

可以枚舉編号 ≤i−1 ≤ i − 1 的人的個數 k k 。這樣編号為ii的人的個數為 j−k j − k 。然而有 cnti c n t i 個人的編号已經被确定為 i i ，是以還要選出j−k−cntij−k−cnti個人。

再考慮有多少個位置可選擇。從 n n 個位置中，去除掉已經被占的位置數（kk），和已經被确定的位置數（ sumi s u m i ），是以有 n−k−sumi n − k − s u m i 個位置可以選擇。

是以得出轉移：

f[i][j]=∑k=0min(n−sumi,j−cnti)f[i−1][k]×Cj−k−cntin−k−sumi f [ i ] [ j ] = ∑ k = 0 min ( n − s u m i , j − c n t i ) f [ i − 1 ] [ k ] × C n − k − s u m i j − k − c n t i

最後答案 f[n][n] f [ n ] [ n ] 。複雜度 O(T×n3) O ( T × n 3 ) 。

Source

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
const int N = ;
int n, m, MX, cnt[N], sum[N], s[N], C[N][N], f[N][N];
void init() {
    int i, j; for (i = ; i <= n; i++) C[i][] = ;
    for (i = ; i <= n; i++) for (j = ; j <= i; j++)
        C[i][j] = (C[i - ][j] + C[i - ][j - ]) % MX;
}
void work() {
    int i, j, k; n = read(); m = read(); MX = read();
    for (i = ; i <= n; i++) cnt[i] = ; init();
    for (i = ; i <= m; i++) read(), cnt[read()]++; sum[n + ] = s[] = ;
    for (i = ; i <= n; i++) s[i] = s[i - ] + cnt[i];
    for (i = ; i <= n; i++) if (s[i] + n - m < i)
        return (void) puts("NO");
    for (i = n; i; i--) sum[i] = sum[i + ] + cnt[i];
    for (i = ; i <= n; i++) for (j = ; j <= n; j++) f[i][j] = ;
    f[][] = ; for (i = ; i <= n; i++) for (j = i; j <= n; j++)
    for (k = ; k <= min(n - sum[i], j - cnt[i]); k++)
        f[i][j] = (f[i][j] + l * f[i - ][k]
            * C[n - k - sum[i]][j - k - cnt[i]] % MX) % MX;
    printf("YES %d\n", f[n][n]);
}
int main() {
    int T = read(); while (T--) work();
    return ;
}
           

T3

分析

設有理數解的集合為 {p1q1,p2q2,p3q3,...,ptqt} { p 1 q 1 , p 2 q 2 , p 3 q 3 , . . . , p t q t } ，那麼可以将原方程分解因式：

(q1x−p1)(q2x−p2)(q3x−p3)...(qtx−pt)ORZ ( q 1 x − p 1 ) ( q 2 x − p 2 ) ( q 3 x − p 3 ) . . . ( q t x − p t ) O R Z

ORZ O R Z 表示不可分解的因式。

設 ORZ O R Z 的常數項為 w w ，最高次項為rr，則一定有：

原方程的最高次項 an=r∏ti=1qi a n = r ∏ i = 1 t q i

原方程的常數項 a0=w∏ti=1(−pi) a 0 = w ∏ i = 1 t ( − p i )

由于上面涉及到的 p p ，qq， w w ，rr等數都是整數，是以最簡分數 pq p q 是原方程解的必要條件是：

p|a0 and q|an p | a 0  and  q | a n

一看系數的絕對值隻有 2×107 2 × 10 7 ， a0 a 0 和 an a n 的約數不多，是以可以枚舉 a0 a 0 和 an a n 的約數求出一個 pq p q ，并判斷 x=pq x = p q 是不是原方程的解。

如何判斷 x=pq x = p q 是不是原方程的解呢？将 x=pq x = p q 代入原方程得到：

∑i=0nai(pq)i ∑ i = 0 n a i ( p q ) i

乘以 qn q n 得到：

∑i=0naipiqn−i ∑ i = 0 n a i p i q n − i

是以 x=pq x = p q 是原方程的解的條件是：

∑i=0naipiqn−i=0 ∑ i = 0 n a i p i q n − i = 0

pi p i 和 qn−i q n − i 的值都很大，使用高精度不好寫又容易TLE，是以考慮用幾個質數取模 （哈希大法好啊！）。

當然，還要特判 a0=0 a 0 = 0 的情況：這時候方程存在一個解 x=0 x = 0 。然後從低次幂向高次幂掃描，如果掃描到 ah≠0 a h ≠ 0 ，就終止掃描，将 ah a h 作為方程的常數項，以此類推，将 ah+i a h + i 作為方程的 i i 次項（0<i≤n−h0<i≤n−h），構成一個一進制 n−h n − h 次方程。然後就和上面一樣了。

注意約分，排序和去重。

Source

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
const int N = , MX =  + , PYZ =  + , LPF = ,
CYX = , CX =  + , CYF = , M =  + ;
struct cyx {
    int x, y;
    cyx() {}
    cyx(int _x, int _y) : x(_x), y(_y) {}
} ans[M], R[M];
bool comp(cyx a, cyx b) {
    double x =  * a.x / a.y, y =  * b.x / b.y;
    return x < y;
}
int qpow(int a, int b, int MX) {
    a = (a % MX + MX) % MX;
    int res = ; while (b) {
        if (b & ) res = l * res * a % MX;
        a = l * a * a % MX; b >>= ;
    }
    return res;
}
int n, b[N], a[N], tot, tot1, a1[M], tot2, a2[M], cnt;
bool check(int p, int q) {
    int i, ans = ; for (i = ; i <= n; i++)
        ans = (ans + l * a[i] * qpow(p, i, MX) % MX
        * qpow(q, n - i, MX) % MX) % MX; if (ans) return ;
    ans = ; for (i = ; i <= n; i++)
        ans = (ans + l * a[i] * qpow(p, i, PYZ) % PYZ
        * qpow(q, n - i, PYZ) % PYZ) % PYZ; if (ans) return ;
    ans = ; for (i = ; i <= n; i++)
        ans = (ans + l * a[i] * qpow(p, i, LPF) % LPF
        * qpow(q, n - i, LPF) % LPF) % LPF; if (ans) return ;
    ans = ; for (i = ; i <= n; i++)
        ans = (ans + l * a[i] * qpow(p, i, CYX) % CYX
        * qpow(q, n - i, CYX) % CYX) % CYX; if (ans) return ;
    ans = ; for (i = ; i <= n; i++)
        ans = (ans + l * a[i] * qpow(p, i, CX) % CX
        * qpow(q, n - i, CX) % CX) % CX; if (ans) return ;
    ans = ; for (i = ; i <= n; i++)
        ans = (ans + l * a[i] * qpow(p, i, CYF) % CYF
        * qpow(q, n - i, CYF) % CYF) % CYF;
    return ans == ;
}
int main() {
    int i, j, t = ; n = read(); for (i = ; i <= n; i++) b[i] = read();
    if (!b[t]) {while (!b[t]) t++; ans[++tot] = cyx(, );}
    for (i = t; i <= n; i++) a[i - t] = b[i]; n -= t;
    int S1 = sqrt(abs(a[])), S2 = sqrt(abs(a[n]));
    for (i = ; i <= S1; i++) if (a[] % i == ) {
        a1[++tot1] = i; a1[++tot1] = -i; if (i * i != abs(a[]))
            a1[++tot1] = a[] / i, a1[++tot1] = -a[] / i;
    }
    for (i = ; i <= S2; i++) if (a[n] % i == ) {
        a2[++tot2] = i; a2[++tot2] = -i; if (i * i != abs(a[n]))
            a2[++tot2] = a[n] / i, a2[++tot2] = -a[n] / i;
        }
    for (i = ; i <= tot1; i++) for (j = ; j <= tot2; j++)
        if (check(a1[i], a2[j])) ans[++tot] = cyx(a1[i], a2[j]);
    for (i = ; i <= tot; i++) {
        int w = __gcd(ans[i].x, ans[i].y);
        ans[i].x /= w; ans[i].y /= w; if (ans[i].y < )
            ans[i].x = -ans[i].x, ans[i].y = -ans[i].y;
    }
    sort(ans + , ans + tot + , comp);
    for (i = ; i <= tot; i++)
        if (i ==  || ans[i].x != ans[i - ].x || ans[i].y != ans[i - ].y)
            R[++cnt] = ans[i]; cout << cnt << endl;
    for (i = ; i <= cnt; i++)
        if (R[i].y == ) printf("%d\n", R[i].x);
        else printf("%d/%d\n", R[i].x, R[i].y);
    return ;
}