【洛谷4920】[WC2015] 未来程序（提答题）

素颜马尾好姑娘i 2021-12-01 14:24 158阅读 0赞

[点此看题面][Link 1]

**大致题意：** 把\$10\$个点的暴力代码和输入数据都给你，让你求出输出数据。

### 子任务\$1\$ ###

第一个子任务自然是拿来送分用的。。。

容易发现就是一个快速乘的过程啊。

代码如下：

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define ull unsigned long long #define Inc(x,y) ((x+=(y))>=X&&(x-=X)) using namespace std; ull a,b,c; I ull Qmul(ull x,ull y,ull X) {ull t=0;W(y) y&1&&Inc(t,x),(x<<=1)%=X,y>>=1;return t;}//快速乘 int main() { freopen("program1.in","r",stdin),freopen("program1.out","w",stdout); RI T=10;W(T--) scanf("%llu%llu%llu",&a,&b,&c),printf("%llu\n",Qmul(a,b,c));return 0;//读入、输出 }

运行结果：

11239440904485 7551029211890 20677492996370 592966462292420 69231182718627 479525534330380 544015996901435 214227311823605 73749675429767 239498441843796

### 子任务\$2\$ ###

题目中给出的式子是：

b = a + b; a = 2 * b - a + c; c = 2 * b - a + c;

逐一代入化简得：

\\\[b=a+b\\\]

\\\[a=2(a+b)-a+c=a+2b+c\\\]

\\\[c=2(a+b)-(a+2b+c)+c=a\\\]

较显然的矩乘板子题。

代码如下：

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define LL long long #define Inc(x,y) ((x+=(y))>=X&&(x-=X)) using namespace std; LL n;int X; class Mat//定义矩阵类 { private: int n,m;LL a[3][3]; public: I Mat(CI x=0,CI y=0):n(x),m(y){for(RI i=0,j;i^x;++i) for(j=0;j^y;++j) a[i][j]=0;} I LL *operator [] (CI x) {return a[x];} I Mat operator * (Mat o) Con//矩阵乘法 { Mat res(n,o.m);RI i,j,k; for(i=0;i^n;++i) for(j=0;j^o.m;++j) for(k=0;k^m;++k) Inc(res[i][j],1LL*a[i][k]*o[k][j]%X); return res; } I Mat operator ^ (LL y) Con//矩阵快速幂 { Mat x=*this,res(n,m);for(RI i=0;i^n;++i) res[i][i]=1; W(y) y&1&&(res=res*x,0),x=x*x,y>>=1;return res; } }; int main() { freopen("program2.in","r",stdin),freopen("program2.out","w",stdout); Mat Base(3,3),res;Base[0][0]=Base[0][2]=Base[1][0]=Base[1][1]=Base[2][0]=1,Base[0][1]=2;//初始化转移矩阵 RI T=10;W(T--) scanf("%lld%d",&n,&X),res=Mat(3,1),res[0][0]=1, res=(Base^n)*res,printf("%d\n",(res[0][0]-2*res[1][0]+res[2][0]+2LL*X)%X);//输出答案 return 0; }

运行结果：

0 1 96 64 2503 2523 4452160 557586868 959316082 1107500137

### 子任务\$3\$ ###

题意显然是求\$0\\sim n\$的\$0\\sim4\$次幂和。

套公式直接算即可，注意此处\$0^0\$貌似等于\$1\$。

考虑到\$unsigned\\ long\\ long\$的自然溢出是向\$2^\{64\}\$取模，这个数不是质数，求逆元不太方便，因此可以考虑使用\$Python\$。

代码如下：

Fin=open("program3.in","r"); Fout=open("program3.out","w"); n=(int)(Fin.read());#读入 mod=2**64;#定义模数 Fout.write((str)((n+1)%mod)+"\n");#0次幂和 Fout.write((str)((n+1)%mod)+"\n"); Fout.write((str)((n*(n+1)//2)%mod)+"\n");#1次幂和 Fout.write((str)((n*(n+1)//2)%mod)+"\n"); Fout.write((str)((n*(n+1)*(2*n+1)//6)%mod)+"\n");#2次幂和 Fout.write((str)((n*(n+1)*(2*n+1)//6)%mod)+"\n"); Fout.write((str)((n*n*(n+1)*(n+1)//4)%mod)+"\n");#3次幂和 Fout.write((str)((n*n*(n+1)*(n+1)//4)%mod)+"\n"); Fout.write((str)((n*(n+1)*(2*n+1)*(3*n*n+3*n-1)//30)%mod)+"\n");#4次幂和 Fout.write((str)((n*(n+1)*(2*n+1)*(3*n*n+3*n-1)//30)%mod)+"\n");

运行结果：

1000000000000001 1000000000000001 2538972135152631808 2538972135152631808 2806098670314569728 2806098670314569728 6570342264898322432 6570342264898322432 10067259324320137216 10067259324320137216

### 子任务\$4\$ ###

分析代码可见，子任务\$4\$以及后面的子任务\$5\$都是根据一个\$01\$矩阵而产生的共\$3\$个问题。

#### 问题\$1\$ ####

求出有多少对点都为\$1\$。

则我们直接求出为\$1\$的点数\$tot\$，然后答案就为\$tot(tot-1)\$。

#### 问题\$2\$ ####

求出到每个为\$1\$的点最近的为\$0\$的点的距离和。

从\$4\$个方向（左上、右上、左下、右下）进行\$DP\$，然后取\$min\$即可。

以从左上方向右下方的\$DP\$为例，转移方程如下：

\\\[f\_\{i,j\}=min(f\_\{i-1,j\},f\_\{i,j-1\})+1\\\]

代码如下

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define N 5000 #define LL long long #define Gmin(x,y) (x>(y)&&(x=(y))) using namespace std; int n,m,ty,seed,a[N+5][N+5]; I int Rand() { static const int P=1000000007,Q=83978833,R=8523467; return seed=(1LL*Q*seed%P*seed+R)%P; } I void Init() { scanf("%d%d%d",&n,&m,&ty); for(RI i=0,j;i^n;++i) for(j=0;j^m;++j) a[i][j]=(Rand()%8)>0; } I LL count1()//解决问题1 { RI i,j,tot=0;for(i=0;i^n;++i) for(j=0;j^m;++j) tot+=a[i][j];//统计为1的点的个数 return 1LL*tot*(tot-1);//计算并返回答案 } int f[N+5][N+5],g[N+5][N+5]; I void Clear() {for(RI i=0,j;i^n;++i) for(j=0;j^m;++j) f[i][j]=a[i][j]?n+m:0;}//清空 I void DP1() {for(RI i=0,j;i^n;++i) for(j=0;j^m;++j) i&&Gmin(f[i][j],f[i-1][j]+1),j&&Gmin(f[i][j],f[i][j-1]+1);}//从左上向右下DP I void DP2() {for(RI i=0,j;i^n;++i) for(j=m-1;~j;--j) i&&Gmin(f[i][j],f[i-1][j]+1),(j+1)^m&&Gmin(f[i][j],f[i][j+1]+1);}//从右上向左下DP I void DP3() {for(RI i=n-1,j;~i;--i) for(j=0;j^m;++j) (i+1)^n&&Gmin(f[i][j],f[i+1][j]+1),j&&Gmin(f[i][j],f[i][j-1]+1);}//从左下向右上DP I void DP4() {for(RI i=n-1,j;~i;--i) for(j=m-1;~j;--j) (i+1)^n&&Gmin(f[i][j],f[i+1][j]+1),(j+1)^m&&Gmin(f[i][j],f[i][j+1]+1);}//从右下向左上DP I LL count2()//解决问题2 { RI i,j;LL ans=0;for(i=0;i^n;++i) for(j=0;j^m;++j) g[i][j]=n+m;//初始化 for(Clear(),DP1(),i=0;i^n;++i) for(j=0;j^m;++j) Gmin(g[i][j],f[i][j]);//DP for(Clear(),DP2(),i=0;i^n;++i) for(j=0;j^m;++j) Gmin(g[i][j],f[i][j]); for(Clear(),DP3(),i=0;i^n;++i) for(j=0;j^m;++j) Gmin(g[i][j],f[i][j]); for(Clear(),DP4(),i=0;i^n;++i) for(j=0;j^m;++j) Gmin(g[i][j],f[i][j]); for(i=0;i^n;++i) for(j=0;j^m;++j) ans+=g[i][j];return ans;//统计并返回答案 } int main() { freopen("program4.in","r",stdin),freopen("program4.out","w",stdout); RI T=10;scanf("%d",&seed);W(T--) Init(),printf("%lld\n",ty?count2():count1());return 0; }

运行结果：

65300 768644095452 1614752 12299725860312 6474661 480452490358302 40508992 480453060258360 40509116 40508835

### 子任务\$5\$ ###

#### 问题\$3\$ ####

求全\$1\$矩形的个数。

考虑枚举右下角，则该行从左往右所能构成的全\$1\$矩阵高度应该是递增的，如：

0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1

这个例子中从左往右全\$1\$矩阵高度应为\$0,0,2,2,2,3,4\$，这可以用**单调栈维护**。

又可以发现，以该位置为右下角的所有全\$1\$矩阵高度和即为以该位置为右下角的全\$1\$矩阵个数。

因此我们只需要在单调栈内元素进出时维护好全\$1\$矩阵高度和即可。

代码如下：

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define N 5000 #define LL long long #define Gmin(x,y) (x>(y)&&(x=(y))) using namespace std; int n,m,ty,seed,a[N+5][N+5]; I int Rand() { static const int P=1000000007,Q=83978833,R=8523467; return seed=(1LL*Q*seed%P*seed+R)%P; } I void Init() { scanf("%d%d",&n,&m); for(RI i=0,j;i^n;++i) for(j=0;j^m;++j) a[i][j]=(Rand()%8)>0; } int S[N+5],V[N+5],f[N+5][N+5]; I LL count3()//解决问题3 { LL ans=0;for(RI i=(S[0]=-1,0),j,t,T;i^n;++i) for(T=t=j=0;j^m;++j) { f[i][j]=a[i][j]?(i?f[i-1][j]:0)+1:0;//求出该位置向上的连续的1的个数 W(T&&f[i][j]<=f[i][S[T]]) t-=V[T--];//维护单调栈，注意弹出元素要清除贡献 S[++T]=j,ans+=(t+=(V[T]=(S[T]-S[T-1])*f[i][j]));//加入元素，计算贡献并统计 }return ans; } int main() { freopen("program5.in","r",stdin),freopen("program5.out","w",stdout); RI T=10;scanf("%d",&seed);W(T--) Init(),printf("%lld\n",count3());return 0; }

运行结果：

36798 780109 4970330 19778353 79444881 183972917 324090457 401682783 493647857 493666110

### 子任务\$6\$ ###

题目中要求的是\$n\$次\$t=at^2+b(mod\\ c)\$后\$t\$的值。

显然其最后必然会出现循环节。

因此我们考虑用\$Brent\$判环来倍增求出循环节，然后就可以快速计算了。

还是比较模板的。

代码如下：

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define ull unsigned long long #define hl_AK_NOI true using namespace std; ull n,a,b,X; int main() { freopen("program6.in","r",stdin),freopen("program6.out","w",stdout); int T=10;W(T--) { ull i,j,t=0,tx=0,ty=2;scanf("%llu%llu%llu%llu",&n,&a,&b,&X),i=j=0; W(hl_AK_NOI)//Brent判环 { if(j=(a*j*j+b)%X,++tx,i==j) break;//找到循环节 tx==ty&&(tx=0,ty<<=1,i=j);//倍增 } i=j=0;W(t^tx) j=(a*j*j+b)%X,++t;//找到循环节的起始位置 t=1;W(i^j) i=(a*i*i+b)%X,j=(a*j*j+b)%X,++t;//计算循环节的长度 t=(n-t)%tx+1;W(t) i=(a*i*i+b)%X,--t;//快速求出答案 printf("%llu\n",i);//输出 }return 0; }

运行结果：

518048760868869048 1792066212437514363 31017889126204134 2107151525961152753 402987993063476955 1026935915030784632 2533709394548916391 1357484894607415330 1099871450072879095 235900336338336004

### 子任务\$7\$ ###

字母版的数独，\$DLX\$板子题。

代码如下：

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while using namespace std; int Case;char a[20][20];struct Operate {int x,y,v;}p[(1<<12)+5]; class DancingLinksX { private: int tot,sz[(1<<10)+5],lnk[(1<<12)+5],res[(1<<8)+5]; struct node { int x,y,u,d,l,r; I node(CI X=0,CI Y=0,CI U=0,CI D=0,CI L=0,CI R=0):x(X),y(Y),u(U),d(D),l(L),r(R){} }O[(1<<14)+5]; I bool Dance(CI x) { #define Delete(x)\ {\ O[O[O[x].l].r=O[x].r].l=O[x].l;\ for(RI i=O[x].d;i^x;i=O[i].d) for(RI j=O[i].r;j^i;j=O[j].r)\ O[O[O[j].u].d=O[j].d].u=O[j].u,--sz[O[j].y];\ } #define Regain(x)\ {\ for(RI i=O[x].d;i^x;i=O[i].d) for(RI j=O[i].r;j^i;j=O[j].r)\ O[O[j].u].d=O[O[j].d].u=j,++sz[O[j].y];\ O[O[x].l].r=O[O[x].r].l=x;\ } if(!O[0].r) { RI i,k;for(i=1;i^x;++i) a[p[res[i]].x][p[res[i]].y]=p[res[i]].v; for(k=1;k<=Case;++k) {for(i=1;i<=16;++i) cout<<(a[i]+1);cout<<endl;}return 1; } RI i,j,t=O[0].r;for(i=O[t].r;i;i=O[i].r) sz[t]>sz[i]&&(t=i); Delete(t);for(i=O[t].d;i^t;i=O[i].d) { for(res[x]=O[i].x,j=O[i].r;j^i;j=O[j].r) Delete(O[j].y); if(Dance(x+1)) return 1; for(j=O[i].l;j^i;j=O[j].l) Regain(O[j].y); }Regain(t);return 0; } public: I void Init(CI x) { RI i;for(tot=x,i=0;i<=x;++i) O[i]=node(0,i,i,i,i-1,i+1); O[O[0].l=x].r=0,memset(lnk,-1,sizeof(lnk)),memset(sz,0,sizeof(sz)); } I void Insert(CI x,CI y) { ++sz[y],O[++tot]=node(x,y,y,O[y].d),O[y].d=O[O[y].d].u=tot, ~lnk[x]?(O[tot].l=lnk[x],O[tot].r=O[lnk[x]].r,O[lnk[x]].r=O[O[lnk[x]].r].l=tot) :(lnk[x]=O[tot].l=O[tot].r=tot); } I void Solve() {!Dance(1)&&(puts("NO SOLUTION."),0);} }DLX; int main() { freopen("program7.in","r",stdin),freopen("program7.out","w",stdout); RI Ttot=4,i,j,k,cnt,t=0;W(Ttot--) { #define P(x,y) ((x-1<<4)+y) #define T(x,y) (((x-1>>2)<<2)+(y+3>>2)) for(++Case,DLX.Init(1<<10),cnt=0,i=1;i<=16;++i) scanf("%s",a[i]+1); for(i=1;i<=16;++i) for(j=1;j<=16;++j) for(k=1;k<=16;++k) { if(a[i][j]^'?'&&(a[i][j]&31)^k) continue; p[++cnt].x=i,p[cnt].y=j,p[cnt].v=64|k, DLX.Insert(cnt,P(i,j)),DLX.Insert(cnt,P(i,k)+256), DLX.Insert(cnt,P(j,k)+512),DLX.Insert(cnt,P(T(i,j),k)+768); }DLX.Solve(); }return 0; }

运行结果：

NAPILFJBMHEOGDCKJDCHMNIPAFGKOBLEKLMGAEHONCDBPJFIFEOBCDGKIJLPAMHNOFHLJMBGEKIDCNAPPCEAHLDFBMJNIKGOBNIKOAPEFGCHJLMDMGDJNIKCLOPAFHEBIOBPFKLJHEMGDANCDKJEIGMAOBNCLFPHGMNCEPOHDLAFKIBJAHLFDBCNPIKJEGOMEIFMBHADKPOLNCJGHPADGJFICNBEMOKLLJKOPCNMGAHIBEDFCBGNKOELJDFMHPIA BLNOMGAPIHJKDCEFHGIMCFBOAPEDKNLJFCAEDKLJBGNOPHMIDKJPHIENFMLCGBAOIBEAKCFLHNOGJMDPLHFNJAPDCIKMEGOBPDOJNMHGELBFAKICCMGKOBIEJADPFLNHOFCHPNMBKJAELIGDJNLDGECHOBFIMPKAGAPIFDOKLCMNHJBEMEKBALJIGDPHOFCNEIBGLPNMDOHJCAFKKPDCEHGANFILBOJMNJHLBOKFMECAIDPGAOMFIJDCPKGBNEHL BLNOMGAPIHJKDCEFHGIMCFBOAPEDKNLJFCAEDKLJBGNOPHMIDKJPHIENFMLCGBAOIBEAKCFLHNOGJMDPLHFNJAPDCIKMEGOBPDOJNMHGELBFAKICCMGKOBIEJADPFLNHOFCHPNMBKJAELIGDJNLDGECHOBFIMPKAGAPIFDOKLCMNHJBEMEKBALJIGDPHOFCNEIBGLPNMDOHJCAFKKPDCEHGANFILBOJMNJHLBOKFMECAIDPGAOMFIJDCPKGBNEHL FMPCJGLEANDBOHKIOEHGNCAMFKILDJPBDBNIFHKPJOGEMACLKALJOIDBCHMPGNEFEGOHPJBKIFNMADLCALFDIENOHJKCBMGPNKCPMFGDBLEAHIJOJIBMHACLODPGEFNKLDIEAPHGNBCOJKFMMHAODLJCPGFKNBIEGPKFEBMNDIAJLCOHBCJNKOFIMELHPGADIOGKCDEHLABNFPMJPFEBLMIAGCJDKOHNHJDLGNPFKMOICEBACNMABKOJEPHFILDG FMPCJGLEANDBOHKIOEHGNCAMFKILDJPBDBNIFHKPJOGEMACLKALJOIDBCHMPGNEFEGOHPJBKIFNMADLCALFDIENOHJKCBMGPNKCPMFGDBLEAHIJOJIBMHACLODPGEFNKLDIEAPHGNBCOJKFMMHAODLJCPGFKNBIEGPKFEBMNDIAJLCOHBCJNKOFIMELHPGADIOGKCDEHLABNFPMJPFEBLMIAGCJDKOHNHJDLGNPFKMOICEBACNMABKOJEPHFILDG FMPCJGLEANDBOHKIOEHGNCAMFKILDJPBDBNIFHKPJOGEMACLKALJOIDBCHMPGNEFEGOHPJBKIFNMADLCALFDIENOHJKCBMGPNKCPMFGDBLEAHIJOJIBMHACLODPGEFNKLDIEAPHGNBCOJKFMMHAODLJCPGFKNBIEGPKFEBMNDIAJLCOHBCJNKOFIMELHPGADIOGKCDEHLABNFPMJPFEBLMIAGCJDKOHNHJDLGNPFKMOICEBACNMABKOJEPHFILDG LDFABIOEGCKJNMHPJPONCFDMLHABIGKEHMEGLJPKFNOIACDBCIKBANHGPMEDFOJLFBMIJPLHAKGEDNCOACJKODIFNLPHBEMGPGHEMBKNDFCOJILAONLDEAGCIJBMPHFKDJIPHOELCAFNGKBMEOGHPMCABIJKLDNFMFACNKJBOGDLEPIHBKNLIGFDMEHPCAOJILCJGHMPKBNAOFEDGHBFDLNOEPMCKJAINAPOKEBJHDIFMLGCKEDMFCAIJOLGHBPN LDFABIOEGCKJNMHPJPONCFDMLHABIGKEHMEGLJPKFNOIACDBCIKBANHGPMEDFOJLFBMIJPLHAKGEDNCOACJKODIFNLPHBEMGPGHEMBKNDFCOJILAONLDEAGCIJBMPHFKDJIPHOELCAFNGKBMEOGHPMCABIJKLDNFMFACNKJBOGDLEPIHBKNLIGFDMEHPCAOJILCJGHMPKBNAOFEDGHBFDLNOEPMCKJAINAPOKEBJHDIFMLGCKEDMFCAIJOLGHBPN LDFABIOEGCKJNMHPJPONCFDMLHABIGKEHMEGLJPKFNOIACDBCIKBANHGPMEDFOJLFBMIJPLHAKGEDNCOACJKODIFNLPHBEMGPGHEMBKNDFCOJILAONLDEAGCIJBMPHFKDJIPHOELCAFNGKBMEOGHPMCABIJKLDNFMFACNKJBOGDLEPIHBKNLIGFDMEHPCAOJILCJGHMPKBNAOFEDGHBFDLNOEPMCKJAINAPOKEBJHDIFMLGCKEDMFCAIJOLGHBPN LDFABIOEGCKJNMHPJPONCFDMLHABIGKEHMEGLJPKFNOIACDBCIKBANHGPMEDFOJLFBMIJPLHAKGEDNCOACJKODIFNLPHBEMGPGHEMBKNDFCOJILAONLDEAGCIJBMPHFKDJIPHOELCAFNGKBMEOGHPMCABIJKLDNFMFACNKJBOGDLEPIHBKNLIGFDMEHPCAOJILCJGHMPKBNAOFEDGHBFDLNOEPMCKJAINAPOKEBJHDIFMLGCKEDMFCAIJOLGHBPN

### 子任务\$8\$ ###

这题看起来像是要推式子（实际上我本来就是要这么做的），但是\$hl666\$神仙告诉我，这其实可以用**拉格朗日插值**。

具体做法就是先暴力求出一开始的几个值，然后插值求出\$n\$位置的答案即可。

很暴力，很直接，但很没问题。

不过要特殊处理第\$1\$个点，容易看出这个点答案就是\$C\_n^7\$，因此一开始的几个值它都为\$0\$，较大的又无法暴力求出，所以不能拉格朗日插值，只能直接计算。

代码如下：

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define X 1234567891 #define LL long long #define ull unsigned LL #define Qinv(x) Qpow(x,X-2) using namespace std; int F[11][12];ull n; I void MakeList(CI n)//暴力求出一开始的几个值 { RI a,b,c,d,e,f,g,q=0,r=0,s=0,t=0,u=0,v=0,w=0,x=0,y=0,z=0; for(a=1;a<=n;++a) for(b=1;b<=n;++b) for(c=1;c<=n;++c) for(d=1;d<=n;++d) for(e=1;e<=n;++e) for(f=1;f<=n;++f) for(g=1;g<=n;++g) a<b&&b<c&&c<d&&d<e&&e<f&&f<g&&++q,a<b&&c<g&&c<d&&e<f&&a<d&&++r, a<d&&d<f&&c<f&&c<e&&b<d&&++s,d<e&&b<d&&a<f&&d<e&&b<g&&++t, c<f&&b<f&&b<c&&f<g&&b<f&&++u,b<d&&b<c&&d<f&&c<e&&b<e&&++v, a<c&&a<b&&c<e&&b<f&&e<g&&++w,b<d&&b<f&&a<g&&c<g&&a<e&&++x, b<f&&a<c&&c<d&&a<c&&b<e&&++y,d<e&&e<f&&a<d&&c<g&&b<d&&++z; F[1][n]=q,F[2][n]=r,F[3][n]=s,F[4][n]=t,F[5][n]=u, F[6][n]=v,F[7][n]=w,F[8][n]=x,F[9][n]=y,F[10][n]=z; } I int Qpow(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}//快速幂 I void Lagrange(int *F,CI l,CI r,Con ull& n)//拉格朗日插值 { if(n<=r) return (void)(printf("%d\n",F[n]));RI i,j,s1,s2;LL res=0; for(i=l;i<=r;++i)//计算 { for(s1=s2=1,j=l;j<=r;++j) i^j&&(s1=1LL*s1*((n-j)%X)%X,s2=1LL*s2*((i-j+X)%X)%X); (res+=1LL*F[i]*s1%X*Qinv(s2)%X)>=X&&(res-=X); }printf("%d\n",res);//输出答案 } int main() { freopen("program8.in","r",stdin),freopen("program8.out","w",stdout); RI i;for(i=4;i<=11;++i) MakeList(i);scanf("%llu",&n);//预处理 RI ans=1;for(i=1;i<=7;++i) ans=1LL*ans*((n-i+1)%X)%X*Qinv(i)%X;printf("%d\n",ans);//特殊处理第1个点 for(i=2;i<=10;++i) Lagrange(F[i],4,11,n);return 0;//拉格朗日插值求出剩余点 }

运行结果：

1018333390 993704934 1053807588 1144151985 712062141 530076748 520686243 337499021 820275783 80253986

### 子任务\$9\$ ###

直接上网找\$MD5\$解密网站或者人类智慧？

这里直接给出答案：

1984 123456 chenlijie $_$ we hold these truths to be selfevident

### 子任务\$10\$ ###

一点开\$cpp\$文件顿时吓懵了：这是什么鬼？

仔细一看其实也并不是很难。

我们单独考虑每个单词，则主要是要求出每个字母最终对答案的贡献。

因此我们可以设\$f\_\{i,j\}\$为**在长度为\$i\$的单词中，第\$j\$个字母最终被调用的次数**。

\$DP\$预处理\$f\$，然后求答案时调用即可。

代码如下：

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define hl_AK_NOI true #define ull unsigned long long using namespace std; const string s[4]=//存下题目中给出的字符串 { "W(); C();","ALGORITHM();","A(); QUICK(); BROWN(); FOX(); JUMPS(); OVER(); THE(); LAZY(); DOG();", "WHEN(); IN(); THE(); COURSE(); OF(); HUMAN(); EVENTS(); IT(); BECOMES(); NECESSARY(); FOR(); ONE(); PEOPLE(); TO(); DISSOLVE(); THE(); POLITICAL(); BANDS(); WHICH(); HAVE(); CONNECTED(); THEM(); WITH(); ANOTHER(); AND(); TO(); ASSUME(); AMONG(); THE(); POWERS(); OF(); THE(); EARTH(); THE(); SEPARATE(); AND(); EQUAL(); STATION(); TO(); WHICH(); THE(); LAWS(); NATURE(); AND(); NATURES(); GOD(); ENTITLE(); THEM(); A(); DECENT(); RESPECT(); TO(); THE(); OPINIONS(); OF(); MANKIND(); REQUIRES(); THAT(); THEY(); SHOULD(); DECLARE(); THE(); CAUSES(); WHICH(); IMPEL(); THEM(); TO(); THE(); SEPARATION();\ WE(); HOLD(); THESE(); TRUTHS(); TO(); BE(); SELFEVIDENT(); THAT(); ALL(); MEN(); ARE(); CREATED(); EQUAL(); THAT(); THEY(); ARE(); ENDOWED(); BY(); THEIR(); CREATOR(); WITH(); CERTAIN(); UNALIENABLE(); RIGHTS(); THAT(); THEY(); ARE(); AMONG(); THESE(); ARE(); LIFE(); LIBERTY(); AND(); THE(); PURSUIT(); OF(); HAPPINESS(); THAT(); TO(); SECURE(); THESE(); RIGHTS(); GOVERNMENTS(); ARE(); INSTITUTED(); AMONG(); THEM(); DERIVING(); THEIR(); JUST(); POWER(); FROM(); THE(); CONSENT(); OF(); THE(); GOVERNED(); THAT(); WHENEVER(); ANY(); FORM(); OF(); GOVERNMENT(); BECOMES(); DESTRUCTIVE(); OF(); THESE(); ENDS(); IT(); IS(); THE(); RIGHT(); OF(); THE(); PEOPLE(); TO(); ALTER(); OR(); TO(); ABOLISH(); IT(); AND(); TO(); INSTITUTE(); NEW(); GOVERNMENT(); LAYING(); ITS(); FOUNDATION(); ON(); SUCH(); PRINCIPLES(); AND(); ORGANIZING(); ITS(); POWERS(); IN(); SUCH(); FORM(); AS(); TO(); THEM(); SHALL(); SEEM(); MOST(); LIKELY(); TO(); EFFECT(); THEIR(); SAFETY(); AND(); HAPPINESS(); PRUDENCE(); INDEED(); WILL(); DICTATE(); THAT(); GOVERNMENTS(); LONG(); ESTABLISHED(); SHOULD(); NOT(); BE(); CHANGED(); FOR(); LIGHT(); AND(); TRANSIENT(); CAUSES(); AND(); ACCORDINGLY(); ALL(); EXPERIENCE(); HATH(); SHOWN(); THAT(); MANKIND(); ARE(); MORE(); DISPOSED(); TO(); SUFFER(); WHILE(); EVILS(); ARE(); SUFFERABLE(); THAN(); T(); RIGHT(); THEMSELVES(); BY(); ABOLISHING(); THE(); FORMS(); TO(); WHICH(); THEY(); ARE(); ACCUSTOMED(); BUT(); WHEN(); A(); LONG(); TRAIN(); OF(); ABUSES(); AND(); USURPATIONS(); PURSUING(); INVARIABLY(); THE(); SAME(); OBJECT(); EVINCES(); A(); DESIGN(); TO(); REDUCE(); THEM(); UNDER(); ABSOLUTE(); DESPOTISM(); IT(); IS(); THEIR(); RIGHT(); IT(); IS(); THEIR(); DUTY(); TO(); THROW(); OFF(); SUCH(); GOVERNMENT(); AND(); TO(); PROVIDE(); NEW(); GUARDS(); FOR(); THEIR(); FUTURE(); SECURITY(); SUCH(); HAS(); BEEN(); THE(); PATIENT(); SUFFERANCE(); OF(); THESE(); COLONIES(); AND(); SUCH(); IS(); NOW(); THE(); NECESSITY(); WHICH(); CONSTRAINS(); THEM(); TO(); ALTER(); THEIR(); FORMER(); SYSTEMS(); OF(); GOVERNMENT(); THE(); HISTORY(); OF(); THE(); PRESENT(); KING(); OF(); GREAT(); BRITAIN(); IS(); USURPATIONS(); ALL(); HAVING(); IN(); DIRECT(); OBJECT(); TYRANNY(); OVER(); THESE(); STATES(); TO(); PROVE(); THIS(); LET(); FACTS(); BE(); SUBMITTED(); TO(); A(); CANDID(); WORLD();\ HE(); HAS(); REFUSED(); HIS(); ASSENT(); TO(); LAWS(); THE(); MOST(); WHOLESOME(); AND(); NECESSARY(); FOR(); THE(); PUBLIC(); GOOD();\ HE(); HAS(); FORBIDDEN(); HIS(); GOVERNORS(); TO(); PASS(); LAWS(); OF(); IMMEDIATE(); AND(); PRESSING(); IMPORTANCE(); UNLESS(); SUSPENDED(); IN(); THEIR(); OPERATION(); TILL(); HIS(); ASSENT(); SHOULD(); BE(); OBTAINED(); AND(); WHEN(); SO(); SUSPENDED(); HE(); HAS(); UTTERLY(); NEGLECTED(); TO(); ATTEND(); THEM();\ HE(); HAS(); REFUSED(); TO(); PASS(); OTHER(); LAWS(); FOR(); THE(); ACCOMMODATION(); OF(); LARGE(); DISTRICTS(); OF(); PEOPLE(); UNLESS(); THOSE(); PEOPLE(); WOULD(); RELINQUISH(); THE(); RIGHT(); OF(); REPRESENTATION(); IN(); THE(); LEGISLATURE(); A(); RIGHT(); INESTIMABLE(); TO(); THEM(); AND(); FORMIDABLE(); TO(); TYRANTS(); ONLY();\ HE(); HAS(); CALLED(); TOGETHER(); LEGISLATIVE(); BODIES(); AT(); PLACES(); UNUSUAL(); UNCOMFORTABLE(); AND(); DISTANT(); FROM(); THE(); DEPOSITORY(); OF(); THEIR(); PUBLIC(); RECORDS(); FOR(); THE(); SOLE(); PURPOSE(); OF(); FATIGUING(); THEM(); INTO(); COMPLIANCE(); WITH(); HIS(); MEASURES();\ HE(); HAS(); DISSOLVED(); REPRESENTATIVE(); HOUSES(); REPEATEDLY(); FOR(); OPPOSING(); WITH(); MANLY(); FIRMNESS(); HIS(); INVASION(); ON(); THE(); RIGHTS(); OF(); THE(); PEOPLE();\ HE(); HAS(); REFUSED(); FOR(); A(); LONG(); TIME(); AFTER(); SUCH(); DISSOLUTION(); TO(); CAUSE(); OTHERS(); TO(); BE(); ELECTED(); WHEREBY(); THE(); LEGISLATIVE(); POWERS(); INCAPABLE(); OF(); ANNIHILATION(); HAVE(); RETURNED(); TO(); THE(); PEOPLE(); AT(); LARGE(); FOR(); THEIR(); EXERCISE(); THE(); STATE(); REMAINING(); IN(); THE(); MEANTIME(); EXPOSED(); TO(); ALL(); THE(); DANGERS(); OF(); INVASION(); FROM(); WITHOUT(); AND(); CONVULSION(); WITHIN();\ HE(); HAS(); ENDEAVORED(); TO(); PREVENT(); THE(); POPULATION(); OF(); THESE(); STATES(); FOR(); THAT(); PURPOSE(); OBSTRUCTING(); THE(); LAWS(); OF(); NATURALIZING(); OF(); FOREIGNERS(); REFUSING(); TO(); PASS(); OTHERS(); TO(); ENCOURAGE(); THEIR(); MIGRATION(); HITHER(); AND(); RAISING(); THE(); CONDITION(); OF(); NEW(); APPROPRIATIONS(); OF(); LANDS();\ HE(); HAS(); OBSTRUCTED(); THE(); ADMINISTRATION(); OF(); JUSTICE(); BY(); REFUSING(); HIS(); ASSENT(); OF(); LAWS(); FOR(); ESTABLISHING(); JUDICIARY(); POWERS();\ HE(); HAS(); MADE(); JUDGES(); DEPENDENT(); ON(); HIS(); WILL(); ALONE(); FOR(); THE(); TENURE(); OF(); THEIR(); OFFICE(); AND(); THE(); AMOUNT(); AND(); PAYMENT(); OF(); THEIR(); SALARY();\ HE(); HAS(); ERECTED(); A(); MULTITUDE(); OF(); NEW(); OFFICERS(); AND(); SENT(); HITHER(); SWARMS(); OF(); OFFICERS(); TO(); HARASS(); OUR(); PEOPLE(); AND(); EAT(); OUT(); OUR(); SUBSTANCES();\ HE(); HAS(); KEPT(); AMONG(); US(); IN(); TIMES(); OF(); PEACE(); STANDING(); ARMIES(); WITHOUT(); THE(); CONSENT(); OF(); OUR(); LEGISLATURES();\ HE(); HAS(); AFFECTED(); TO(); RENDER(); THE(); MILITARY(); INDEPENDENT(); OF(); AND(); SUPERIOR(); TO(); THE(); CIVIL(); POWER();\ HE(); HAS(); COMBINED(); WITH(); OTHERS(); TO(); SUBJECT(); US(); TO(); A(); JURISDICTION(); FOREIGN(); TO(); OUR(); CONSTITUTION(); AND(); UNACKNOWLEDGED(); BY(); OUR(); LAWS(); GIVING(); HIS(); ASSENT(); TO(); THEIR(); ACTS(); OF(); PRETENDED(); LEGISLATION();\ FOR(); QUARTERING(); LARGE(); BODIES(); OF(); ARMED(); TROOPS(); AMONG(); US();\ FOR(); PROTECTING(); THEM(); BY(); A(); MOCK(); TRIAL(); FROM(); PUNISHMENT(); FOR(); ANY(); MURDER(); WHICH(); THEY(); SHOULD(); COMMIT(); ON(); THE(); INHABITANTS(); OF(); THESE(); STATES();\ FOR(); CUTTING(); OFF(); OUR(); TRADE(); WITH(); ALL(); PARTS(); OF(); THE(); WORLD();\ FOR(); IMPOSING(); TAXES(); ON(); US(); WITHOUT(); OUR(); CONSENT();\ FOR(); DEPRIVING(); US(); IN(); MANY(); CASES(); OF(); THE(); BENEFITS(); OF(); TRIAL(); BY(); JURY();\ FOR(); TRANSPORTING(); US(); BEYOND(); SEAS(); TO(); BE(); TRIED(); FOR(); PRETENDED(); OFFENSES();\ FOR(); ABOLISHING(); THE(); FREE(); SYSTEMS(); OF(); ENGLISH(); LAWS(); IN(); A(); NEIGHBORING(); PROVINCE(); ESTABLISHING(); THEREIN(); AN(); ARBITRARY(); GOVERNMENT(); AND(); ENLARGING(); ITS(); BOUNDARIES(); SO(); AS(); TO(); RENDER(); IT(); AT(); ONCE(); AN(); EXAMPLE(); AND(); FIT(); INSTRUMENT(); FOR(); INTRODUCING(); THE(); SAME(); ABSOLUTE(); RULE(); THESE(); COLONIES();\ FOR(); TAKING(); AWAY(); OUR(); CHARTERS(); ABOLISHING(); OUR(); MOST(); VALUABLE(); LAWS(); AND(); ALTERING(); FUNDAMENTALLY(); THE(); FORMS(); OF(); OUR(); GOVERNMENTS();\ FOR(); SUSPENDING(); OUR(); OWN(); LEGISLATURES(); AND(); DECLARING(); THEMSELVES(); INVESTED(); WITH(); POWER(); TO(); LEGISLATE(); FOR(); US(); IN(); ALL(); CASES(); WHATSOEVER();\ HE(); HAS(); ABDICATED(); GOVERNMENT(); HERE(); BY(); DECLARING(); US(); OUT(); OF(); HIS(); PROTECTION(); AND(); WAGING(); WAR(); AGAINST(); US();\ HE(); HAS(); PLUNDERED(); OUR(); SEAS(); RAVAGED(); OUR(); COASTS(); BURNT(); OUR(); TOWNS(); AND(); DESTROYED(); THE(); LIVES(); OF(); OUR(); PEOPLE();\ HE(); IS(); AT(); THIS(); TIME(); TRANSPORTING(); LARGE(); ARMIES(); OF(); FOREIGN(); MERCENARIES(); TO(); COMPLETE(); THE(); WORKS(); OF(); DEATH(); DESOLATION(); AND(); TYRANNY(); ALREADY(); BEGUN(); WITH(); CIRCUMSTANCES(); OF(); CRUELTY(); AND(); PERFIDY(); SCARCELY(); PARALLEL(); IN(); THE(); MOST(); BARBAROUS(); AGES(); AND(); TOTALLY(); UNWORTHY(); THE(); HEAD(); OF(); A(); CIVILIZED(); NATION();\ HE(); HAS(); CONSTRAINED(); OUR(); FELLOW(); CITIZENS(); TAKEN(); CAPTIVE(); ON(); THE(); HIGH(); SEAS(); TO(); BEAR(); ARMS(); AGAINST(); THEIR(); COUNTRY(); TO(); BECOME(); THE(); EXECUTIONERS(); OF(); THEIR(); FRIENDS(); AND(); BRETHREN(); OR(); TO(); FALL(); THEMSELVES(); BY(); THEIR(); HANDS();\ HE(); HAS(); EXCITED(); DOMESTIC(); INSURRECTION(); AMONGST(); US(); AND(); HAS(); ENDEAVORED(); TO(); BRING(); ON(); THE(); INHABITANTS(); OF(); OUR(); FRONTIERS(); THE(); MERCILESS(); INDIAN(); SAVAGES(); WHOSE(); KNOWN(); RULE(); OF(); WARFARE(); IS(); AN(); UNDISTINGUISHED(); DESTRUCTION(); OF(); ALL(); AGES(); SEXES(); AND(); CONDITIONS();\ IN(); EVERY(); STAGE(); OF(); THESE(); OPPRESSIONS(); WE(); HAVE(); PETITIONED(); FOR(); REDRESS(); IN(); THE(); MOST(); HUMBLE(); TERMS(); OUR(); REPEATED(); PETITION(); HAVE(); BEEN(); ANSWERED(); ONLY(); BY(); REPEATED(); INJURY(); A(); PRINCE(); WHOSE(); CHARACTER(); IS(); THUS(); MARKED(); BY(); EVERY(); ACT(); WHICH(); MAY(); DEFINE(); A(); TYRANT(); IS(); UNFIT(); TO(); BE(); THE(); RULER(); OF(); A(); FREE(); PEOPLE();\ NOR(); HAVE(); WE(); BEEN(); WANTING(); IN(); ATTENTION(); TO(); OUR(); BRITISH(); BRETHREN(); WE(); HAVE(); WARNED(); THEM(); FROM(); TIME(); TO(); TIME(); OF(); ATTEMPTS(); BY(); THEIR(); LEGISLATURE(); TO(); EXTEND(); AN(); UNWARRANTABLE(); JURISDICTION(); OVER(); US(); WE(); HAVE(); REMINDED(); THEM(); OF(); THE(); CIRCUMSTANCES(); OF(); OUR(); EMIGRATION(); AND(); SETTLEMENT(); HERE(); WE(); HAVE(); APPEALED(); TO(); THEIR(); NATIVE(); JUSTICE(); AND(); MAGNANIMITY(); AND(); WE(); HAVE(); CONJURED(); THEM(); BY(); THE(); TIES(); OF(); OUR(); COMMON(); KINDRED(); TO(); DISAVOW(); THESE(); USURPATION(); WHICH(); WOULD(); INEVITABLY(); INTERRUPT(); OUR(); CONNECTIONS(); AND(); CORRESPONDENCE(); THEY(); TOO(); HAVE(); BEEN(); DEAF(); TO(); THE(); VOICE(); OF(); JUSTICE(); AND(); OF(); CONSANGUINITY(); WE(); MUST(); THEREFORE(); ACQUIESCE(); IN(); THE(); NECESSITY(); WHICH(); DENOUNCES(); OUR(); SEPARATION(); AND(); HOLD(); THEM(); AS(); WE(); HOLD(); THE(); REST(); OF(); MANKIND(); ENEMIES(); IN(); WAR(); IN(); PEACE(); FRIENDS();\ WE(); THEREFORE(); THE(); REPRESENTATIVES(); OF(); THE(); UNITED(); STATES(); OF(); AMERICA(); IN(); GENERAL(); CONGRESS(); ASSEMBLED(); APPEALING(); TO(); THE(); SUPREME(); JUDGE(); OF(); THE(); WORLD(); FOR(); THE(); RECTITUDE(); OF(); OUR(); INTENTIONS(); DO(); IN(); THE(); NAME(); AND(); BY(); AUTHORITY(); OF(); THE(); GOOD(); PEOPLE(); OF(); THESE(); COLONIES(); SOLEMNLY(); PUBLISH(); AND(); DECLARE(); THAT(); THESE(); UNITED(); STATES(); COLONIES(); AND(); INDEPENDENT(); STATES(); THAT(); THEY(); ARE(); ABSOLVED(); BY(); FROM(); ALL(); ALLEGIANCE(); TO(); THE(); BRITISH(); CROWN(); AND(); THAT(); ALL(); POLITICAL(); CONNECTION(); BETWEEN(); THEM(); AND(); THE(); STATE(); THEY(); HAVE(); FULL(); POWER(); TO(); LEVY(); WAR(); CONCLUDE(); PEACE(); CONTRACT(); ALLIANCES(); ESTABLISH(); COMMERCE(); AND(); TO(); DO(); ALL(); OTHER(); ACTS(); AND(); THINGS(); WHICH(); INDEPENDENT(); STATES(); MAY(); OF(); RIGHT(); DO(); AND(); FOR(); THE(); SUPPORT(); OF(); THIS(); DECLARATION(); WITH(); A(); FIRM(); RELIANCE(); ON(); THE(); PROTECTION(); OF(); DIVINE(); PROVIDENCE(); WE(); MUTUALLY(); PLEDGE(); TO(); EACH(); OTHER(); OUR(); LIVES(); OUR(); FORTUNES(); AND(); OUR(); SACRED(); HONOR();\ A(); QUICK(); BROWN(); FOX(); JUMPS(); OVER(); THE(); LAZY(); DOG();\ ALGORITHM();" }; const int Times[4]={1,2,2,5};int n;ull a[30],f[20][20]; int main() { freopen("program10.in","r",stdin),freopen("program10.out","w",stdout); RI T,i,j,l,r;ull ans;string t; for(a[0]=i=1;i<=26;++i) for(a[i]=(27-i)*a[i-1],j=0;j<i-1;++j) a[i]+=a[j];//处理每个字母调用_()的次数 for(f[1][1]=1,i=2;i<=15;++i) for(j=1;j<=i;++j)//DP求出长度为i的单词中第j个字母被调用的次数 for(l=1;l<=j;++l) for(r=j;r<=i;++r) (l^1||r^i)&&(f[i][j]+=f[r-l+1][j-l+1]); for(T=0;T^4;++T) { scanf("%d",&n),ans=l=0,r=s[T].length();W(hl_AK_NOI) { t="";W(l^r&&!isalpha(s[T][l])) ++l;if(l==r) break; W(l^r&&isalpha(s[T][l])) t+=s[T][l++];//枚举单词 for(i=0,j=t.length();i^j;++i) ans+=1ull*a[t[i]&31]*f[j][i+1];//统计答案 } for(i=0;i^Times[T];++i) printf("%llu\n",ans*n);//输出 }return 0; }

运行结果：

6754098618987872142 12891177331947568152 12891177331947568152 14433265847896447980 14433265847896447980 15363876303000165384 15363876303000165384 15363876303000165384 15363876303000165384 15363876303000165384

### 附录：答案 ###

最后，我把每个子任务的答案综合了一下，放在下面的链接中：

[点击下载答案][Link 2]

转载于:https://www.cnblogs.com/chenxiaoran666/p/Luogu4920.html

[Link 1]: https://www.luogu.org/problemnew/show/P4920
[Link 2]: https://files.cnblogs.com/files/chenxiaoran666/%E3%80%90%E6%B4%9B%E8%B0%B74920%E3%80%91Answer.zip