自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:26:13，当前版本为作者最后更新于2021-06-15 14:21:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这篇题解有点水。

因为只有六重循环，所以答案最多是关于 $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;
}