2020 CCPC網路選拔賽部分題解

1002 Graph Theory Class

題意：給n個結點1,2,…n，i和j之間的邊權是lcm(i+1,j+1)，問最小生成樹邊權和
解題思路：讓所有結點變成2,3,4…n+1.這樣把其中所有質數向2連邊，所有合數向它的因子連邊，這樣答案為[3,n+1]數字和+[3,n+1]質數和，然后套min25板子就行，難點是需要知道min25板子（

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;
int k;
typedef long long LL;

namespace Min25 {

    int prime[N], id1[N], id2[N], flag[N], ncnt, m;

    LL g[N], sum[N], a[N], T, n;

    inline int ID(LL x) {
        return x <= T ? id1[x] : id2[n / x];
    }

    inline LL calc(LL x) {
        return x * (x + 1) / 2 - 1;
    }

    inline void init() {
        //for(int i=0;i<N;++i) prime[i]=id1[i]=id2[i]=flag[i]=g[i]=sum[i]=a[i]=0;
        ncnt=0;m=0;
        T = sqrt(n + 0.5);
        for (int i = 2; i <= T; i++) {
            if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;
            for (int j = 1; j <= ncnt && i * prime[j] <= T; j++) {
                flag[i * prime[j]] = 1;
                if (i % prime[j] == 0) break;
            }
        }
        for (LL l = 1; l <= n; l = n / (n / l) + 1) {
            a[++m] = n / l;
            if (a[m] <= T) id1[a[m]] = m; else id2[n / a[m]] = m;
            g[m] = calc(a[m]) % k;
        }
        for (int i = 1; i <= ncnt; i++)
            for (int j = 1; j <= m && (LL)prime[i] * prime[i] <= a[j]; j++)
                g[j] = (g[j] - (((LL)prime[i]%k) * (g[ID(a[j] / prime[i])] - sum[i - 1])%k) +k)%k;
    }

    inline LL solve(LL x) {
        if (x <= 1) return x;
        return n = x, init(), g[ID(n)];
    }

}

int main() {
    int T;
    scanf("%d",&T);
    while(T--)
    {
        LL n; scanf("%lld%d", &n,&k);
        LL tmp=Min25::solve(n+1);
        tmp=(tmp-2+k)%k;
        tmp=(tmp+(((3+n+1)%k)*((n-1)%k))/2)%k;
        cout<<tmp<<endl;
    }
    //printf("%lld\n", Min25::solve(n));
}

1003 Express Mail Taking

水題

#include<bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f
#define all(x) (x).begin(),(x).end()
#define PII pair<int,int>
#define FOR(i,a,b) for(int i=a;i<b;++i) 
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
#ifdef LOCAL 
const int maxn=30; 
#else
const int maxn=1e6+5;
#endif
int a[maxn];
int n,m,k;
void init()
{
    scanf("%d%d%d",&n,&m,&k);
    FOR(i,0,m) scanf("%d",a+i);
    sort(a,a+m);
}
void sol()
{
    int pos=1;
    LL ans=0;
    for(int i=m-1;i>=0;--i)
    {
        ans+=abs(pos-k);
        ans+=abs(a[i]-k);
        pos=a[i];
    }
    ans+=abs(pos-1);
    cout<<ans<<'\n';
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        sol();
    }
    return 0;
}

1005 Lunch

題意：有n個數字，每次操作可以選擇一個數字x，把它變成k個x/k（k是x的因子），選擇的x不可以是1.當全場只有1則輸了
解題思路：
對于一個l來說，它由若干個質因子組成，對于奇數質因子，比如t，取了之后，t被拆成t個l/t，因為t是奇數，其實相當于變成了1個l/t的情況，所以l最多操作它的（奇數質因子個數）次，會變成 2 x 2^x 2x的形式，而變成 2 x 2^x 2x的時候，只要x不為0，那么不管怎么取都會變成必敗態，也就是說， 2 x 2^x 2x對應了nim博弈種只剩下1個石頭的狀態，
那么（奇數質因子個數+ [l為偶數])就是當前局面可以操作的最多次數，對應nim博弈中的石子個數，可以理解為，如果取k = 偶數，相當于把整塊石子拿完，取奇數則取多少個奇數質因子對應了取多少個石子，
然后就轉化成了nim博弈問題，求異或和就好了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100;
int isp[maxn], p[maxn];
int main(void) {
    int N = 100010;
    for (int i=2;i<=N;i++) {
        if (isp[i] == 0) p[++p[0]] = i;
        for (int j=1;j<=p[0] && i*p[j]<=N;j++) {
            isp[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
    int T; scanf("%d",&T);
    while (T--) {
        int n; scanf("%d",&n);
        int ans = 0;
        for (int i=1;i<=n;i++) {
            int l; scanf("%d",&l);
            int g=0;
            if (l%2==0) {
                g++;
                while (l%2==0) l/=2;
            }
            for (int j=2;p[j]*p[j]<=l;j++) if (l%p[j]==0) {
                g++, l/=p[j];
                while (l%p[j] == 0) g++, l/=p[j];
            }
            if (l > 1) g++;
            ans ^= g;
        }
        if (ans) printf("W\n");
        else printf("L\n");
    }
    return 0;
}

1006 Robotic Class

不是我寫的，當我正在翻看它長長的題面的時候小伙伴已經開始敲起了代碼（
據說是直接模擬題意，

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, K[505];
int a[505][2020],b[505][2020],c[505][2020],d[505][2020];
ll gao(int t, ll x, int cc) {
    if (t == n) return x;
    int pos = lower_bound(a[t],a[t]+K[t],x) - a[t];
    if (pos < K[t] && x == a[t][pos] && cc == 1) pos++;
    return gao(d[t][pos], c[t][pos]*(ll)x+b[t][pos], c[t][pos]*cc);
}
int main(void) {
    //freopen("f.in","r",stdin);
    int T; scanf("%d",&T);
    for (int cas=1;cas<=T;cas++) {
        printf("Case #%d: ",cas);
        scanf("%d",&n);
        for (int i=1;i<n;i++) {
            scanf("%d",&K[i]);
            for (int j=0;j<=K[i];j++) {
                scanf("%d%d%d",&c[i][j],&b[i][j],&d[i][j]);
                if (j < K[i]) scanf("%d",&a[i][j]);
            }
        }
        int f=1;
        for (int i=n-1;i>=1;i--) {
            for (int j=0;j<K[i];j++) {
                ll left = gao(i, a[i][j], -1);
                ll right = gao(i, a[i][j], 1);
                ll mid = gao(i, a[i][j], 0);
                if (left != right || left != mid) {
                    f=0;
                    break;
                }
            }
            if (f == 0) break;
        }
        if (f) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}

1007 CCPC Training Class

題意：對于字串S，定義Border(S)為S最長的不為S的前綴使得該前綴是S的后綴，
定義D(S) = D(Border(S))+1，當S為空則D(S) = 0
給一個字串，可以重排它們，設重排出來的串是 t 1 t 2 t 3 . . . t n t_1t_2t_3...t_n t1?t2?t3?...tn?，設T[i] = t 1 t 2 . . . t i t_1t_2...t_i t1?t2?...ti?，求 M a x ( D ( T [ i ] ) ) ( 1 < = i < = n ) Max(D(T[i])) \ (1<=i<=n) Max(D(T[i])) (1<=i<=n)最大可以是多少
解題思路：一看榜單這么多人過，看樣例猜一個出現最多次的字母次數，敢交敢過，

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define fors(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
int a[26];
const int maxn = 2e5 + 50;
char s[maxn];
int main()
{
    int T; cin>>T;
    int ca = 0;
    while(T--){
        scanf("%s", s);
        memset(a,0,sizeof a);
        int ans = 0;
        int len = strlen(s);
        fors(i,0,len) ans = max(ans, ++a[s[i]-'a']);
        printf("Case #%d: %d\n",++ca, ans);
    }
}

1010 Reports

真 · 簽到

1011 3x3 Convolution

題意：給一個n * n的矩陣，然后和另一個3 * 3的卷積核一直做卷積，a[i][j]以(i,j)位置作為3 * 3的左上角來卷積
解題思路：如果不是左上角為1的卷積核，則一定會產生流失導致最終全部為0.

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define fors(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
const int maxn = 55;
int a[maxn][maxn];
int b[3][3];
int n;
int main()
{
    int T; cin>>T;
    while(T--){
        scanf("%d", &n);
        fors(i,0,n)
            fors(j,0,n) scanf("%d", &a[i][j]);
        int f = 1;
        fors(i,0,3) fors(j,0,3){
            scanf("%d", &b[i][j]);
            if(i==0&&j==0){
                if(b[i][j] == 0) f = 0;
            }else{
                if(b[i][j] > 0) f = 0;
            }
        }
        if(f){
            fors(i,0,n)
                fors(j,0,n) {
                    printf("%d", a[i][j]);
                    if(j==n-1) printf("\n");
                    else printf(" ");
                }
        }else{
            fors(i,0,n)
                fors(j,0,n) {
                    printf("0");
                    if(j==n-1) printf("\n");
                    else printf(" ");
                }
        }
    }
}

1012 Xor

以前寫過差不多的，
稍微改一下就是這題

1013 Residual Polynomial

題意：給一個多項式 f ( x ) = ∑ i = 0 n a i x i f(x) = \sum_{i=0}^n a_ix^i f(x)=∑i=0n?ai?xi
f i ( x ) = b i f i ? 1 ′ ( x ) + c i f i ? 1 f_i(x) = b_if_{i-1}'(x)+c_if_{i-1} fi?(x)=bi?fi?1′?(x)+ci?fi?1?
f 1 ( x ) = f ( x ) f_1(x) = f(x) f1?(x)=f(x)
求 f n ( x ) f_n(x) fn?(x)的每個系數.
解題思路：以 f 1 f_1 f1?為基礎一步一步化開觀察
( f n ( x ) f^n(x) fn(x)代表對 f ( x ) f(x) f(x)求n階導)
f 2 ( x ) = b 2 f 1 ( x ) + c 2 f ( x ) f_2(x)=b_2f^1(x)+c_2f(x) f2?(x)=b2?f1(x)+c2?f(x)
f 3 ( x ) = b 2 b 3 f 2 ( x ) + ( b 2 c 3 + b 3 c 2 ) f 1 ( x ) + c 2 c 3 f ( x ) f_3(x)=b_2b_3f^2(x)+(b_2c_3+b_3c_2)f^1(x)+c_2c_3f(x) f3?(x)=b2?b3?f2(x)+(b2?c3?+b3?c2?)f1(x)+c2?c3?f(x)
f 4 ( x ) = b 2 b 3 b 4 f 3 ( x ) + ( b 2 b 3 c 4 + b 3 b 4 c 2 + b 2 b 4 c 3 ) f 2 ( x ) + ( c 2 c 3 b 4 + c 3 c 4 b 2 + c 2 c 4 b 3 ) f 1 ( x ) + c 2 c 3 c 4 f ( x ) f_4(x)=b_2b_3b_4f^3(x)+(b_2b_3c_4+b_3b_4c_2+b_2b_4c_3)f^2(x)+(c_2c_3b_4+c_3c_4b_2+c_2c_4b_3)f^1(x)+c_2c_3c_4f(x) f4?(x)=b2?b3?b4?f3(x)+(b2?b3?c4?+b3?b4?c2?+b2?b4?c3?)f2(x)+(c2?c3?b4?+c3?c4?b2?+c2?c4?b3?)f1(x)+c2?c3?c4?f(x)
可以發現， f n n ( x ) f_n^n(x) fnn?(x)的運算式中， f i ( x ) f^i(x) fi(x)的系數對應 ∏ i = 2 n ( b i x + c i ) \prod_{i=2}^n(b_ix+c_i) ∏i=2n?(bi?x+ci?)中 x i x^i xi的系數,設為 p i p_i pi?，這個東西可以分治NTT求出來，
設最終 x i x^i xi的系數為 w i w_i wi?
則可得 w i = ∑ i + j = k p j ? a k ? ∏ t = i + 1 k t w_i=\sum_{i+j=k} p_j*a_k*\prod_{t=i+1}^{k} t wi?=∑i+j=k?pj??ak??∏t=i+1k?t
后面那個乘積部分對于每個 w i w_i wi?不統一，改寫一下：
則可得 w i ? i ! = ∑ i + j = k p j ? a k ? k ! w_i*i!=\sum_{i+j=k} p_j*a_k*k! wi??i!=∑i+j=k?pj??ak??k!
讓 a [ i ] = a [ n ? i ] ? ( n ? i ) ! a[i] = a[n-i]*(n-i)! a[i]=a[n?i]?(n?i)!，則每個 i ! w i i!w_i i!wi?也可以通過p和修改后的a卷積求出了，

以下是通過代碼，跑的挺慢，不推薦當作分治NTT的板子，

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int maxn = 2e5 + 50;
const int mod = 998244353;
int qm(int a, int b){int res = 1; while(b){if(b&1) res = (ll)res*a%mod; a = (ll)a*a%mod; b >>= 1; } return res; }
int mulwn[maxn<<2], invwn[maxn<<2];
int fac[maxn], ifac[maxn];
void INIT(){
    fac[0] = ifac[0] = 1;
    for(int i = 1; i < maxn; ++i) fac[i] = (ll)fac[i-1]*i%mod, ifac[i] = qm(fac[i], mod-2);

    for(ll i=1;i < maxn*4;i<<=1) mulwn[i]=qm(3,(mod-1)/i);
    for(ll i=1;i < maxn*4;i<<=1) invwn[i]=qm(mulwn[i],mod-2);
}
struct NTT {
    int n, m, rev[maxn << 2];
    int a[maxn << 2], b[maxn << 2];
    void init(int len) {
        for (n = 1, m = 0; n < len + len; n <<= 1, m++);
        for (int i = 0; i < n; ++i) {
            rev[i] = (rev[i >> 1] >> 1) | (i & 1) << (m - 1);
            a[i] = 0;
            b[i] = 0;
        }
    }
    void ntt(int *a, int f) {//
        for (int i = 0; i < n; ++i)if (i < rev[i])swap(a[i], a[rev[i]]);

        for (int k = 2; k <= n; k <<= 1) {
            int wn=(f>0)?mulwn[k]:invwn[k];
            int mid = k>>1;
            for(int i = 0; i < n; i += k){
                int w = 1;
                for(int j = 0; j < mid; ++j, w = (ll)w*wn%mod){
                    int temp = ((ll)w*a[i+j+mid])%mod;
                    a[i+j+mid] = (a[i+j]-temp+mod)%mod;
                    a[i+j] = (a[i+j]+temp)%mod;
                }
            }
        }
        return;
    }
    void Calculate() {
        ntt(a, 1); ntt(b, 1);
        for (int i = 0; i < n; ++i)a[i] = (ll)a[i]*b[i]%mod;//??μ?è??￡
        ntt(a, -1);
        int invl = qm(n, mod-2);
        for(int i = 0; i < n; ++i){
            a[i] = (ll)a[i]*invl%mod;
        }
    }
} F;
int n;
int a[maxn], b[maxn], c[maxn];
void init()
{
    cin>>n;
    for(int i = 0; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 2; i <= n; ++i) scanf("%d", &b[i]);
    for(int i = 2; i <= n; ++i) scanf("%d", &c[i]);
}
vector<int> w[maxn<<2];
void work(int rt, int l, int r){
    w[rt].clear();
    if(l == r){
        w[rt].pb(c[l]); w[rt].pb(b[l]);
        return;
    }
    int mid = (r+l)>>1;
    work(rt<<1, l, mid);
    work(rt<<1|1, mid+1, r);
    int len = w[rt<<1].size() + w[rt<<1|1].size()-1;
    if(r-l+1<=1000){
        for(int i = 0; i < len; ++i) w[rt].pb(0);
        for(int i = 0; i < w[rt<<1].size(); ++i){
            for(int j = 0; j < w[rt<<1|1].size(); ++j){
                w[rt][i+j] = (w[rt][i+j] + (ll)w[rt<<1][i]*w[rt<<1|1][j]%mod)%mod;
            }
        }
        w[rt<<1].clear(); w[rt<<1|1].clear();
        return;
    }
    F.init(len);
    for(int i = 0; i < w[rt<<1].size(); ++i) F.a[i] = w[rt<<1][i];
    for(int i = 0; i < w[rt<<1|1].size(); ++i) F.b[i] = w[rt<<1|1][i];
    w[rt<<1].clear(); w[rt<<1|1].clear();
    F.Calculate();
    for(int i = 0; i < len; ++i){
        w[rt].push_back(F.a[i]);
    }
    return;
}

void sol(){
    work(1,2,n);//w[rt][i] * a[j]
    int len = w[1].size() + n;
    F.init(len);
    for(int i = 0; i < w[1].size(); ++i) {
        F.a[i] = w[1][i];
        //cout<<"i:"<<i<<" val:"<<w[1][i]<<endl;
    }
    for(int i = 0; i <= n; ++i) F.b[i] = (ll)a[n-i]*fac[n-i]%mod;
    F.Calculate();
    for(int i = 0; i <= n; ++i) {
        int ans = (ll)F.a[n-i]*ifac[i]%mod;
        printf("%d", ans);
        if(i == n) printf("\n");
        else printf(" ");
    }
}
int main(){

    INIT();
    int T; cin>>T;
    while(T--){
        init();
        sol();
    }
}
/*
3
3
0 0 0 1
1 1
1 1
*/