[NWRRC2015] Fygon 题解

· · 题解

这篇题解有点水。

因为只有六重循环，所以答案最多是关于 n 的六次多项式。

只需要求出 0,1,2,3,4,5,6 处的点值再插值回去就行了。

求点值直接暴力，而插值这里我采用了范德蒙德矩阵的逆，我直接打出了 7\times 7 的表，实际上想要算的话可以看我上一篇题解里的链接 https://www.luogu.com.cn/blog/ix-35/solution-p7016。

注意分数类运算。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=45;
struct Frac {
    Frac (int a=0,int b=0) {x=a,y=b;}
    ll x,y;
}px[MAXN],py[MAXN],xs[MAXN];
int n,m,l,sj[MAXN],op[MAXN],ox[MAXN],oy[MAXN],nv[MAXN];
ll v[7][7]={  // 这表大概是范德蒙德逆矩阵的一个分子，具体的有点忘了
{720,-1764,1624,-735,175,-21,1},
{0,-720,1044,-580,155,-20,1},
{0,-360,702,-461,137,-19,1},
{0,-240,508,-372,121,-18,1},
{0,-180,396,-307,107,-17,1},
{0,-144,324,-260,95,-16,1},
{0,-120,274,-225,85,-15,1}};
ll b[7]={720,-120,48,-36,48,-120,720};
string s;
ll gcd (ll a,ll b) {return (b?gcd(b,a%b):a);}
Frac yf (Frac a) {
    if (a.x==0) {a.y=1;return a;}
    ll tmp=gcd(a.y,a.x);
    a.y/=tmp,a.x/=tmp;
    return a;
}
Frac add (Frac a,Frac b) {
    ll tmp=gcd(a.y,b.y);
    tmp=a.y/tmp*b.y;
    Frac c;
    c.y=tmp;
    c.x=a.x*(tmp/a.y)+b.x*(tmp/b.y);
    return yf(c);
}
Frac neg (Frac a) {
    a.x*=-1,a.y*=-1;
    return yf(a);
}
Frac minus (Frac a,Frac b) {
    return yf(add(a,neg(b)));
}
Frac mult (Frac a,Frac b) {
    Frac c;
    c.x=a.x*b.x,c.y=a.y*b.y;
    return yf(c);
}
Frac ds (Frac a) {
    swap(a.x,a.y);
    return yf(a);
}
Frac divs (Frac a,Frac b) {
    return yf(mult(a,ds(b)));
}
int solve (int l,int r,int in) {
    if (l==r) {return 1;}
    int las=l,res=0;
    for (int i=l+1;i<=r;i++) {
        if (sj[i]==in) {
            if (op[las]==1) {
                for (int j=0;j<nv[oy[las]];j++) {
                    nv[ox[las]]=j;
                    res+=solve(las+1,i-1,in+1);
                }
            } else {
                res++;
            }
            las=i;
        }
    }
    if (op[las]==1) {
        for (int j=0;j<nv[oy[las]];j++) {
            nv[ox[las]]=j;
            res+=solve(las+1,r,in+1);
        }
    } else {
        res++;
    }
    //cout << l << "  " << r << "  " << res << endl;
    return res;
}
int main () {
    int nw=0;
    while (getline(cin,s)) {
        l=s.length();
        int cur=0;
        nw++;
        while (s[cur]==' ') {
            cur+=4;
            sj[nw]++;
        }
        if (s[cur]=='l') {op[nw]=2;}
        else {
            op[nw]=1;
            ox[nw]=s[cur+4]-'a'+10;
            oy[nw]=(s[cur+15]>='a'&&s[cur+15]<='z')?(s[cur+15]-'a'+10):(s[cur+15]-'0');
        }
    }
    for (int i=1;i<=9;i++) {nv[i]=i;}
    for (int i=0;i<=6;i++) {
        nv['n'-'a'+10]=i;
        px[i]=Frac(i,1);
        int tmp=solve(1,nw,0);
        py[i]=Frac(tmp,1);
    }
    for (int i=0;i<=6;i++) {
        xs[i].y=1;
        for (int j=0;j<=6;j++) {
            xs[i]=add(xs[i],divs(mult(py[j],Frac(v[j][i],1)),Frac(b[j],1)));
        }
    }
    for (int j=6;j>=0;j--) {
        if (xs[j].x<0) {
            xs[j].x*=-1,xs[j].y*=-1;
        }
        if (xs[j].y<0) {printf("-");xs[j].y*=-1;}
        else if (j<6) {printf("+");}
        printf("%lld/%lld",xs[j].x,xs[j].y);
        for (int k=1;k<=j;k++) {printf("*n");}
    }
    return 0;
}