比赛地址
Pro: 4/6/11
Rank: 119/1090
[A] Social Distancing
题意
在半径为r的圆形区域内(含边界)放置n个人,要求每个人都必须在整点上,且要使\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}d(i,j)最小.d(i,j)表示两个人间的欧氏距离.求这个最小值.
题解
遗传算法乱搞打表题.
其实容易猜到一个结论,那就是所有的人一定会站在边界的整点上.在此基础上乱搞的时候会少很多状态.
代码
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstring>
struct Po
{
int x, y;
Po(void) { }
Po(int x, int y):x(x), y(y){ }
int operator |(const Po &o) const
{
return (x-o.x)*(x-o.x) + (y-o.y)*(y-o.y);
}
} p[5000];
int pnt;
int n, r;
constexpr int N(6000), IT(1000), FR(127), FRC(FR*2);
constexpr double p_cr(1./N), p_mu(0.5), greedy(0.6);
constexpr int PN(int(N*greedy));
constexpr int seed(168392710);
std::mt19937 _eng((srand(seed), seed));
#define randuint(ub) (unsigned(_eng()) % unsigned(ub))
#define rand0or1() (rand() > (RAND_MAX>>1))
#define rand0to1() (double(_eng()) / UINT_MAX)
struct Agent
{
int g[8];
int eval() const
{
int sum = 0;
for (int i=0; i<n-1; ++i)
for (int j=i+1; j<n; ++j)
sum += p[g[i]] | p[g[j]];
return sum;
}
bool operator <(const Agent &o) const
{
return eval() > o.eval();
}
Agent cross(const Agent &o) const
{
Agent baby;
int k;
for (int i=0; i<n; ++i)
baby.g[i] = rand0or1() ? g[i] : o.g[i];
return baby;
}
Agent mutate() const
{
Agent clone;
memcpy(clone.g, g, sizeof(g));
clone.g[randuint(n)] = randuint(pnt);
return clone;
}
void println() const
{
printf("[ ");
for (int i=0; i<n; ++i)
printf("(%d, %d)%s", p[g[i]].x, p[g[i]].y, i==n-1 ? "" : " - ");
printf(" ]\n");
}
} gen[500000];
int sta[100], top;
int maxds;
void dfs()
{
if (top == n)
{
int sum = 0;
for (int i=0; i<n-1; ++i)
for (int j=i+1; j<n; ++j)
sum += p[sta[i]] | p[sta[j]];
if (sum > maxds)
maxds = sum;
return;
}
for (int i=0; i<5; ++i)
sta[top++]=i, dfs(), sta[--top]=0;
}
int PopBasedSearch(bool quiet=false)
{
if (n == 1)
return 0;
if (n == 2)
return (r+r) * (r+r);
int gt = 0;
if (n == 4)
gt = (r+r) * (r+r) * 2 + 2*r*r * 4;
pnt = 0;
for (int x=-r; x<=r; ++x) for (int y=-r; y<=r; ++y)
if (x*x+y*y <= r*r)
p[pnt++] = Po(x, y);
if (r == 1)
{
top = maxds = 0;
dfs();
return maxds;
}
if (not quiet) printf("PBS begin, N=%d, IT=%d, p_cr=%.3f, p_mu=%.3f\n", N, IT, p_cr, p_mu);
for (char _: " ")
std::random_shuffle(p, p+pnt);
int a[5000];
for (int i=0; i<pnt; ++i)
a[i] = i;
for (int i=0; i<N; ++i)
std::random_shuffle(a, a+pnt), memcpy(gen[i].g, a, sizeof(gen[i].g));
int best_ans = 0;
int conti = 0;
for (int it=0; it<IT; ++it)
{
int cur = N;
for (int i=0; i<N-1; ++i)
for (int j=i+1; j<N; ++j)
if (rand0to1() < p_cr)
gen[cur++] = gen[i].cross(gen[j]);
for (int i=0; i<N; ++i)
if (rand0to1() < p_mu)
gen[cur++] = gen[i].mutate();
std::sort(gen, gen+cur);
std::random_shuffle(gen+PN, gen+cur);
int top1 = gen[0].eval();
if (top1 > best_ans)
best_ans = top1, conti = 0;
else
++conti;
if (conti > FRC)
break;
if (!(it & FR) or it == IT-1)
if (not quiet) printf("[%.2f%%]: cur=%d, top1=%d, his best=%d\n", (it+1.)/IT*100, cur, top1, best_ans);
}
if (conti <= FRC)
printf("(danger!!) ");
if (n == 4 && gt != best_ans)
printf("(danger!! gt=%d) ", gt);
return best_ans;
}
void table()
{
for (n=1; n<=8; ++n)
{
for (r=1; r<=30; ++r)
{
printf("ans[%-2d][%-2d]=%-4d, ", n, r, PopBasedSearch(true));
if (r % 6 == 0)
puts("");
}
}
}
int ans[10][40];
int main()
{
memset(ans, -1, sizeof(ans));
// table();
ans[1 ][1 ]=0 , ans[1 ][2 ]=0 , ans[1 ][3 ]=0 , ans[1 ][4 ]=0 , ans[1 ][5 ]=0 , ans[1 ][6 ]=0 ,
ans[1 ][7 ]=0 , ans[1 ][8 ]=0 , ans[1 ][9 ]=0 , ans[1 ][10]=0 , ans[1 ][11]=0 , ans[1 ][12]=0 ,
ans[1 ][13]=0 , ans[1 ][14]=0 , ans[1 ][15]=0 , ans[1 ][16]=0 , ans[1 ][17]=0 , ans[1 ][18]=0 ,
ans[1 ][19]=0 , ans[1 ][20]=0 , ans[1 ][21]=0 , ans[1 ][22]=0 , ans[1 ][23]=0 , ans[1 ][24]=0 ,
ans[1 ][25]=0 , ans[1 ][26]=0 , ans[1 ][27]=0 , ans[1 ][28]=0 , ans[1 ][29]=0 , ans[1 ][30]=0 ,
ans[2 ][1 ]=4 , ans[2 ][2 ]=16 , ans[2 ][3 ]=36 , ans[2 ][4 ]=64 , ans[2 ][5 ]=100 , ans[2 ][6 ]=144 ,
ans[2 ][7 ]=196 , ans[2 ][8 ]=256 , ans[2 ][9 ]=324 , ans[2 ][10]=400 , ans[2 ][11]=484 , ans[2 ][12]=576 ,
ans[2 ][13]=676 , ans[2 ][14]=784 , ans[2 ][15]=900 , ans[2 ][16]=1024 , ans[2 ][17]=1156 , ans[2 ][18]=1296 ,
ans[2 ][19]=1444 , ans[2 ][20]=1600 , ans[2 ][21]=1764 , ans[2 ][22]=1936 , ans[2 ][23]=2116 , ans[2 ][24]=2304 ,
ans[2 ][25]=2500 , ans[2 ][26]=2704 , ans[2 ][27]=2916 , ans[2 ][28]=3136 , ans[2 ][29]=3364 , ans[2 ][30]=3600 ,
ans[3 ][1 ]=8 , ans[3 ][2 ]=32 , ans[3 ][3 ]=76 , ans[3 ][4 ]=130 , ans[3 ][5 ]=224 , ans[3 ][6 ]=312 ,
ans[3 ][7 ]=416 , ans[3 ][8 ]=554 , ans[3 ][9 ]=722 , ans[3 ][10]=896 , ans[3 ][11]=1064 , ans[3 ][12]=1248 ,
ans[3 ][13]=1512 , ans[3 ][14]=1746 , ans[3 ][15]=2016 , ans[3 ][16]=2264 , ans[3 ][17]=2600 , ans[3 ][18]=2888 ,
ans[3 ][19]=3218 , ans[3 ][20]=3584 , ans[3 ][21]=3912 , ans[3 ][22]=4344 , ans[3 ][23]=4712 , ans[3 ][24]=5138 ,
ans[3 ][25]=5612 , ans[3 ][26]=6062 , ans[3 ][27]=6536 , ans[3 ][28]=6984 , ans[3 ][29]=7520 , ans[3 ][30]=8084 ,
ans[4 ][1 ]=16 , ans[4 ][2 ]=64 , ans[4 ][3 ]=144 , ans[4 ][4 ]=256 , ans[4 ][5 ]=400 , ans[4 ][6 ]=576 ,
ans[4 ][7 ]=784 , ans[4 ][8 ]=1024 , ans[4 ][9 ]=1296 , ans[4 ][10]=1600 , ans[4 ][11]=1936 , ans[4 ][12]=2304 ,
ans[4 ][13]=2704 , ans[4 ][14]=3136 , ans[4 ][15]=3600 , ans[4 ][16]=4096 , ans[4 ][17]=4624 , ans[4 ][18]=5184 ,
ans[4 ][19]=5776 , ans[4 ][20]=6400 , ans[4 ][21]=7056 , ans[4 ][22]=7744 , ans[4 ][23]=8464 , ans[4 ][24]=9216 ,
ans[4 ][25]=10000, ans[4 ][26]=10816, ans[4 ][27]=11664, ans[4 ][28]=12544, ans[4 ][29]=13456, ans[4 ][30]=14400,
ans[5 ][1 ]=24 , ans[5 ][2 ]=96 , ans[5 ][3 ]=218 , ans[5 ][4 ]=384 , ans[5 ][5 ]=624 , ans[5 ][6 ]=880 ,
ans[5 ][7 ]=1188 , ans[5 ][8 ]=1572 , ans[5 ][9 ]=2014 , ans[5 ][10]=2496 , ans[5 ][11]=2984 , ans[5 ][12]=3520 ,
ans[5 ][13]=4224 , ans[5 ][14]=4870 , ans[5 ][15]=5616 , ans[5 ][16]=6336 , ans[5 ][17]=7224 , ans[5 ][18]=8056 ,
ans[5 ][19]=9008 , ans[5 ][20]=9984 , ans[5 ][21]=10942, ans[5 ][22]=12080, ans[5 ][23]=13144, ans[5 ][24]=14326,
ans[5 ][25]=15624, ans[5 ][26]=16896, ans[5 ][27]=18184, ans[5 ][28]=19488, ans[5 ][29]=20968, ans[5 ][30]=22480,
ans[6 ][1 ]=36 , ans[6 ][2 ]=144 , ans[6 ][3 ]=324 , ans[6 ][4 ]=576 , ans[6 ][5 ]=900 , ans[6 ][6 ]=1296 ,
ans[6 ][7 ]=1764 , ans[6 ][8 ]=2304 , ans[6 ][9 ]=2916 , ans[6 ][10]=3600 , ans[6 ][11]=4356 , ans[6 ][12]=5184 ,
ans[6 ][13]=6084 , ans[6 ][14]=7056 , ans[6 ][15]=8100 , ans[6 ][16]=9216 , ans[6 ][17]=10404, ans[6 ][18]=11664,
ans[6 ][19]=12996, ans[6 ][20]=14400, ans[6 ][21]=15876, ans[6 ][22]=17424, ans[6 ][23]=19044, ans[6 ][24]=20736,
ans[6 ][25]=22500, ans[6 ][26]=24336, ans[6 ][27]=26244, ans[6 ][28]=28224, ans[6 ][29]=30276, ans[6 ][30]=32400,
ans[7 ][1 ]=48 , ans[7 ][2 ]=192 , ans[7 ][3 ]=432 , ans[7 ][4 ]=768 , ans[7 ][5 ]=1224 , ans[7 ][6 ]=1740 ,
ans[7 ][7 ]=2356 , ans[7 ][8 ]=3102 , ans[7 ][9 ]=3954 , ans[7 ][10]=4896 , ans[7 ][11]=5872 , ans[7 ][12]=6960 ,
ans[7 ][13]=8280 , ans[7 ][14]=9564 , ans[7 ][15]=11016, ans[7 ][16]=12456, ans[7 ][17]=14160, ans[7 ][18]=15816,
ans[7 ][19]=17666, ans[7 ][20]=19584, ans[7 ][21]=21500, ans[7 ][22]=23688, ans[7 ][23]=25808, ans[7 ][24]=28122,
ans[7 ][25]=30624, ans[7 ][26]=33120, ans[7 ][27]=35664, ans[7 ][28]=38266, ans[7 ][29]=41200, ans[7 ][30]=44076,
ans[8 ][1 ]=64 , ans[8 ][2 ]=256 , ans[8 ][3 ]=576 , ans[8 ][4 ]=1024 , ans[8 ][5 ]=1600 , ans[8 ][6 ]=2304 ,
ans[8 ][7 ]=3136 , ans[8 ][8 ]=4096 , ans[8 ][9 ]=5184 , ans[8 ][10]=6400 , ans[8 ][11]=7744 , ans[8 ][12]=9216 ,
ans[8 ][13]=10816, ans[8 ][14]=12544, ans[8 ][15]=14400, ans[8 ][16]=16384, ans[8 ][17]=18496, ans[8 ][18]=20736,
ans[8 ][19]=23104, ans[8 ][20]=25600, ans[8 ][21]=28224, ans[8 ][22]=30976, ans[8 ][23]=33856, ans[8 ][24]=36864,
ans[8 ][25]=40000, ans[8 ][26]=43264, ans[8 ][27]=46656, ans[8 ][28]=50176, ans[8 ][29]=53824, ans[8 ][30]=57600;
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d %d", &n, &r);
printf("%d\n", ans[n][r]);
}
return 0;
}
[B] Mask Allocation
题意
有n\times m个口罩,要求把它们分成尽可能少的k箱,同时这k箱可以分成n组,每组共有m个口罩,或者是m组,每组共有n个口罩.输出方案.
题解
不妨设n>m.先把所有的口罩分成m箱,每一箱n个.然后将每一箱拆分成很多小箱,每一小箱有m个,这样最后会余下m箱,每箱n\%m个口罩,然后将m看做n,n\%m看做m,用类似辗转相除的方法继续划分,直到最后余数为0.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int ans[2000005], tot;
int main(){
int T; cin >> T; while(T--) {
int n, m; scanf("%d%d", &n, &m);
if (n > m) n ^= m ^= n ^= m;
tot = 0;
while(n != 0) {
int t = m / n;
for (int i = 1; i <= t; i++) for (int j = 1; j <= n; j++) ans[++tot] = n;
int p = m % n;
m = n; n = p;
}
printf("%d\n", tot);
for (int i = 1; i <= tot; i++) printf("%d ", ans[i]); printf("\n");
}
return 0;
}
[C] A National Pandemic
题意
给一棵树,每个点有一个权值,初始时都是0.有三种操作:
- 给出x和w,对于任意一个点y,其权值增加w-dis(x,y)
- 调整x的权值,如果其大于0,则将其修改为0
- 查询x的权值
题解
对式子做一下变形,w-dis(x,y)=w-dep(x)-dep(y)+2*dep(lca).其中w-dep(x)是每个点共有的增量,可以用一个变量记录.-dep(y)可以用操作1的次数来代替.
开一个线段树来维护最后一部分的增量.+2*dep(lca)可以转化为将点x到根的路径上的所有点的增量+2,然后每个点的增量可以通过查询其到根路径上所有点的增量和来完成.
对于2操作,设置一个偏移量即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 50010
#define INF 0x3f3f3f3f
using namespace std;
int T,n,i,op,x,y,m,lsum=1,cnt;
LL sum,s;
int head[N],top[N],w[N],size[N],hsize[N],hson[N],d[N],fa[N];
LL a[N];
struct Tree{
LL l,r,d,lz;
}t[N*4];
struct Edge{
int t,next;
}e[N*8];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Add(int s,int t){
e[lsum].t=t; e[lsum].next=head[s]; head[s]=lsum++;
}
IL void Maketree(int x,int low,int high){
reg int mid=(low+high)>>1;
t[x].l=low; t[x].r=high;
t[x].d=t[x].lz=0;
if (low==high) return;
Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
}
IL void Push(int x){
reg LL p=t[x].lz;
t[l(x)].lz+=p; t[r(x)].lz+=p;
t[l(x)].d+=(t[l(x)].r-t[l(x)].l+1)*p;
t[r(x)].d+=(t[r(x)].r-t[r(x)].l+1)*p;
t[x].lz=0;
}
IL int Query(int x,int low,int high){
reg int mid=(t[x].l+t[x].r)>>1;
if (t[x].l==low && t[x].r==high) return t[x].d;
if (t[x].lz) Push(x);
if (high<=mid) return Query(l(x),low,high);
else if (low>mid) return Query(r(x),low,high);
else return Query(l(x),low,mid)+Query(r(x),mid+1,high);
}
IL void Add(int x,int low,int high){
reg int mid=(t[x].l+t[x].r)>>1;
if (t[x].l==low && t[x].r==high){
t[x].d+=(t[x].r-t[x].l+1)*2;
t[x].lz+=2; return;
}
if (t[x].lz) Push(x);
if (high<=mid) Add(l(x),low,high);
else if (low>mid) Add(r(x),low,high);
else Add(l(x),low,mid),Add(r(x),mid+1,high);
t[x].d=t[l(x)].d+t[r(x)].d;
}
IL void Dfs(int x,int f){
reg int i=0;
size[x]++;
for (i=head[x];i;i=e[i].next){
if (e[i].t==f) continue;
d[e[i].t]=d[x]+1; fa[e[i].t]=x;
Dfs(e[i].t,x);
if (size[e[i].t]>size[hson[x]]) hson[x]=e[i].t;
size[x]+=size[e[i].t];
}
}
IL void Cut(int x){
reg int i=0;
w[x]=++cnt;
if (hson[x]){
top[hson[x]]=top[x]; Cut(hson[x]);
} else return;
for (i=head[x];i;i=e[i].next){
if (e[i].t==hson[x] || e[i].t==fa[x]) continue;
top[e[i].t]=e[i].t; Cut(e[i].t);
}
}
IL void Ready(){
Maketree(1,1,n);
for (i=1;i<=n;i++) a[i]=size[i]=hson[i]=hsize[i]=top[i]=w[i]=fa[i]=0;
d[1]=top[1]=1; cnt=fa[1]=0; sum=s=0;
Dfs(1,0); Cut(1);
}
IL void Inc(){
x=read(); y=read();
s++; sum+=y-d[x];
while (x){
Add(1,w[top[x]],w[x]);
x=fa[top[x]];
}
}
IL void Change(){
reg LL p=0;
reg int q=0;
q=x=read();
while (q){
p+=Query(1,w[top[q]],w[q]);
q=fa[top[q]];
}
p=p-(LL)d[x]*s+sum+a[x];
if (p<=0) return;
a[x]+=-p;
}
IL void Find(){
reg LL p=0;
reg int q=0;
q=x=read();
while (q){
p+=Query(1,w[top[q]],w[q]);
q=fa[top[q]];
}
// cout<<p<<" "<<s<<" "<<sum<<" "<<a[x]<<endl;
// cout<<sum<<" !"<<endl;
p=p-(LL)d[x]*s+sum+a[x];
printf("%lld\n",p);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
n=read(); m=read();
lsum=1;
for (i=1;i<=n;i++) head[i]=0;
for (i=1;i<n;i++){
x=read(); y=read();
Add(x,y); Add(y,x);
}
Ready();
while (m--){
op=read();
if (op==1) Inc();
else if (op==2) Change();
else Find();
}
}
return 0;
}
[D] Fake News
题意
判断\frac{n(n+1)(2n+1)}{6}是不是完全平方数.
题解
只有在n=1,24的时候才是完全平方数.证明很繁琐,见这里
代码
#include <iostream>
#include <cstdio>
#define GC getchar()
#define PC putchar
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
#define se(x) _Q_(x)else if(_c==EOF)return 0;_H_(x)
int main()
{
unsigned long long n;
int T;
sc(T)
while (T--)
{
sc(n)
puts(n==1ull || n==24ull ? "Fake news!":"Nobody knows it better than me!");
}
return 0;
}
[H] Dividing
题意
给出合法元组的定义:
- $(1,k)$是合法元组
- 若(n,k)是合法元组,则(n+k,k)是合法元组
- 若(n,k)是合法元组,则(nk,k)是合法元组
给出n,k,求有多少对1 \leq x \leq n,1 \leq y \leq k,(x,y)是合法元组.
题解
不难发现,当且仅当x\%y=0/1时才是合法元组.然后数论分块算就行了.
注意特判的时候也要取模......
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const long long int mo = 1000000007;
long long int ans[20000005];
int main(){
long long int n, k; cin >> n >> k;
if (n == 1) {
printf("%lld\n", k%mo);
return 0;
}
long long int nn = n % mo;
ans[1] = nn;
for (long long int i = 2; i <= 20000000; i++) {
long long int t = n/i;
if (n == t * i) ans[i] = (ans[i-1] + n/i*2) % mo;
else ans[i] = (ans[i-1] + n/i*2+1) % mo;
}
if (k <= 20000000) {
printf("%lld\n", ans[k]);
return 0;
}
long long int b = (long long int)(pow(n, 0.5));
long long int down = n/b, nowans = ans[down];
for (long long int i = b-1; i >= 1; i--) {
long long int tim = n/i - n/(i+1);
if (k - down < tim) nowans = (nowans + ((k-down)%mo) * (2*i+1)) % mo;
else {
nowans = (nowans + (tim%mo) * (2*i+1)) % mo;
if (n/i*i==n) nowans = (nowans + mo - 1) % mo;
}
down += tim;
if (down >= k) break;
}
if (down >= k) {
printf("%lld\n", nowans);
return 0;
}
printf("%lld\n", (nowans+k-n)%mo);
return 0;
}
[I] Valuable Forests
题意
定义由n个带标号的点构成的森林的价值为,每个点的度数的平方和的总和.
求由n个点构成的所有森林的价值总和.
题解
很不错的一个树学题.
解题的核心是Prufer数列.Prufer数列告诉我们,每个带标号的无根树和一个长度为n-2的Prufer序列一一对应.
定义f[n]表示,由n个点构成的森林有多少种.为了避免计数重复,可以单独考虑最后一个点所在的树的大小,假如从前n-1个点取出了i个点与最后一个点构成了一棵树的话,不难得到如下递推式:
f[n]=\sum_{i=0}^{n}C_{n-1}^{i}p[i+1]f[n-1-i]
其中p[n]=n^{n-2},也就是n个点构成的无根树的种类数.
再设s[n]表示由n个点构成的所有树的价值总和.因为节点是带标号的,可以一个个单独计算,有如下式子:
s[n]=\sum_{1}^{n}\sum_{d=1}^{n-1}d^{2}C_{n-2}^{d-1}(n-1)^{n-2-(d-1)}
至此就可以递推计算答案了.
设ans[n]表示题目中要求的答案,则有:
ans[n]=\sum_{i=0}^{n-1}(s[i+1]\times f[n-i-1]+ans[n-i-1]p[i+1])
也就是将最后组出来的树单独算贡献,再和前面的森林的贡献加到一起.
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 5010
#define INF 0x3f3f3f3f
using namespace std;
LL T,MOD,i,j,x;
LL c[N][N],p[N],ans[N],f[N],s[N];
IL LL read(){
LL p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
LL Mi(LL x,LL y){
LL p=x,t=1,Res=1;
for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
return Res;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read(); MOD=read();
p[0]=p[1]=p[2]=1;
for (i=3;i<=5000;i++) p[i]=Mi(i,i-2);
c[1][1]=c[1][0]=c[0][0]=c[0][1]=1;
for (i=2;i<=5000;i++){
c[i][0]=1;
for (j=1;j<=i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
}
f[0]=f[1]=1;
for (i=2;i<=5000;i++)
for (j=0;j<i;j++)
f[i]=(f[i]+(p[j+1]*c[i-1][j]%MOD)*f[i-j-1]%MOD)%MOD;
s[0]=s[1]=0;
for (i=2;i<=5000;i++){
for (j=1;j<i;j++)
s[i]=(s[i]+(j*j%MOD)*(c[i-2][j-1]*Mi(i-1,i-j-1)%MOD)%MOD)%MOD;
s[i]=i*s[i]%MOD;
}
ans[0]=ans[1]=0; ans[2]=2;
for (i=3;i<=5000;i++)
for (j=0;j<i;j++){
x=(p[j+1]*ans[i-j-1]%MOD+f[i-j-1]*s[j+1]%MOD)%MOD;
ans[i]=(ans[i]+x*c[i-1][j]%MOD)%MOD;
}
while (T--){
x=read();
printf("%lld\n",ans[x]);
}
return 0;
}
总结
需要多做题,对知识点的运用不够熟练.(说的就是Prufer数列)
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2020牛客暑期多校第七场
本文地址: 2020牛客暑期多校第七场
