A
B 找下规律发现答案是[2,n+1]的和加上[2,n+1]的素数和再减$4$, 直接min_25
C 队友过的
D
E
根据SG定理可以得到$SG(n)=mathop{mex} {SG(frac{n}{d})oplus ...oplus SG(frac{n}{d}) } $, 异或$d$次, $d$是$n$的因子
只有$d$为奇数时有贡献, 所以$SG(n)=mathop{mex}limits_{d|n, ext{$d$为奇}} { SG(frac{n}{d}) }$
找下规律就可以得到 $SG(pn)=SG(n)+1, p>2$
$n$为偶时, $SG(2n)=SG(n)$, $n$为奇时, $SG(2n)=SG(n)+1$
筛一下素因子即可
#include <bits/stdc++.h> #define ctz __builtin_ctzll typedef long long ll; using namespace std; mt19937 rd(time(0)); const int p[12]={2,3,5,7,11,13,17,19,23,29,31,37}; const int p_cnt=12; ll mmul(ll a,ll b,ll m) { //a*b%m ll d=((long double)a/m*b+1e-8); ll r=a*b-d*m; return r<0?r+m:r; } ll FastPow(ll a,ll b,ll m) { ll ans=1; for (;b;b>>=1,a=mmul(a,a,m)) if (b&1) ans=mmul(ans,a,m); return ans; } ll gcd(ll a,ll b) { if (!a||!b) return a+b; int t=ctz(a|b); a>>=ctz(a); do { b>>=ctz(b); if (a>b) swap(a,b); b-=a; } while (b); return a<<t; } int isprime(ll n) { if (n==1) return 0; if (n==2||n==3||n==5) return 1; if (!(n&1)||!(n%3)||!(n%5)) return 0; ll m=n-1; int k=0; while (!(m&1)) m>>=1,++k; for (int ip=0;ip<p_cnt&&p[ip]<n;++ip) { ll x=FastPow(p[ip],m,n),y=x; for (int i=0;i<k;++i) { x=mmul(x,x,n); if (x==1&&y!=1&&y!=n-1) return 0; y=x; } if (x!=1) return 0; } return 1; } ll f[110]; int cnt; ll g(ll x,ll n,ll a) { ll t=mmul(x,x,n)+a; return t<n?t:t-n; } const int M=(1<<7)-1; ll Pollard_Rho(ll n) { if (!(n&1)) return 2; if (!(n%3)) return 3; if (!(n%5)) return 5; ll x=0,y=x,t=1,q=1,a=(rd()%(n-1))+1; for (int k=2;;k<<=1,y=x,q=1) { for (int i=1;i<=k;++i) { x=g(x,n,a); q=mmul(q,abs(x-y),n); if (!(i&M)) { t=gcd(q,n); if (t>1) break; } } if (t>1||(t=gcd(q,n))>1) break; } if (t==n) { t=1; while (t==1) t=gcd(abs((x=g(x,n,a))-y),n); } return t; } void work(ll n) { if (n==1) return; if (isprime(n)) f[++cnt]=n; else { ll t=n; while (t==n) t=Pollard_Rho(n); work(t),work(n/t); } } const int N = 1e5+10; int n; ll a[N]; int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); int ans = 0; for(int i=1;i<=n;++i) { scanf("%lld", a+i); cnt = 0; work(a[i]); int sg = 0, ok = 0; for (int j=1; j<=cnt; ++j) { if (f[j]==2) ok = 1; else ++sg; } sg += ok; ans ^= sg; } puts(ans?"W":"L"); } }
F
G 队友过的
H
设${dp}_{n,i}$表示从n层第$i$扇门走到$(0,0)$的最小期望, 那么有两种方案
一种是一直往左走遍历每扇门, 如果门开着就往下走, 如果左边全关就再绕到右边
另一种就是先右再左, 两种方案取最小就是最优期望
预处理一下概率和距离, 然后转移的时候暴力枚举走到下一层哪个点, 这样复杂度是$O(n^4)$已经可以通过
然后可以发现假设当前层从第$i$扇门出去, 走到下一层的点最优范围是$[i-2,i+1]$, 复杂度就为$O(n^3)$
#include <bits/stdc++.h> using namespace std; const int N = 55; int n,x0,k[N],pos[N][N]; bool vis[N][N]; double dp[N][N],C[N][N],dis[N][N][N],D[N][N][N]; double dfs(int n, int m) { double &ans = dp[n][m]; if (vis[n][m]) return ans; vis[n][m] = 1; if (n==1) return ans = 1; double lx = 0, rx = 0; //先往左走到头再往右走 int cnt = 0, tot = 0; //cnt为查看过的关上的门数, tot为当前走的距离 auto gao = [&](int i) { //p为限定cnt扇门没开, 当前门开的概率 double p = D[n][cnt][k[n]], mi = 1e18; for (int j=max(1,i-2); j<=min(n-1,i+1); ++j) mi = min(mi, dfs(n-1,j)+dis[n][i][j]); return p*(mi+tot); }; for (int i=m; i>=1; --i) { if (cnt+k[n]>n) break; lx += gao(i); if (i!=1) tot += 2; ++cnt; } if (m!=n) { //从1移动到m+1 tot += m*2; for (int i=m+1; i<=n; ++i) { if (cnt+k[n]>n) break; lx += gao(i); tot += 2, ++cnt; } } //先往右走到头再往左走 cnt = tot = 0; for (int i=m; i<=n; ++i) { if (cnt+k[n]>n) break; rx += gao(i); if (i!=n) tot+=2; ++cnt; } if (m!=1) { //从n走到m-1 tot += (n-m+1)*2; for (int i=m-1; i>=1; --i) { if (cnt+k[n]>n) break; rx += gao(i); tot += 2, ++cnt; } } return ans=min(lx,rx); } void work() { scanf("%d%d", &n, &x0); for (int i=1; i<=n; ++i) scanf("%d", k+i); memset(vis,0,sizeof vis); double ans = 1e18; for (int i=1; i<=n; ++i) { double w = sqrt((x0-pos[n][i])*(x0-pos[n][i])+1); ans = min(ans, dfs(n,i)+w); } printf("%.20lf ", ans); } int main() { for (int i=0; i<N; ++i) { C[i][0] = 1; for (int j=1; j<=i; ++j) { C[i][j] = C[i-1][j]+C[i-1][j-1]; pos[i][j] = -i+2*j-1; } } for (int n=1; n<=50; ++n) { for (int i=1; i<=n; ++i) for (int j=1; j<n; ++j) { double x1 = pos[n][i], y1 = n; double x2 = pos[n-1][j], y2 = n-1; dis[n][i][j] = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } for (int k=1; k<=n; ++k) for (int cnt=0; cnt+k<=n; ++cnt) { D[n][cnt][k] = (C[n-cnt][k]-C[n-cnt-1][k])/C[n][k]; } } int t; scanf("%d", &t); while (t--) work(); }
I
J 队友过的
K
若只有$K_{1,1}$非零, 直接输出$A$, 否则输出全零矩阵
L
cometoj原题
异或很容易处理, 绝对值可以拆开, 表示成$x-y+Kge 0wedge y-x+Kge 0$
从二进制高位到低位遍历, 如果当前位$x-y+Kle -2$, 那么后面无论怎么取都是负的, 如果当前位$x-y+Kge 1$, 那么后面无论怎么取都是正的
所以只要维护[-1,1]三种取值即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[32][3][3][2][2][2]; int main() { int t; scanf("%d", &t); while (t--) { int a,b,k,w; scanf("%d%d%d%d", &a, &b, &k, &w); memset(dp,0,sizeof dp); dp[31][1][1][1][1][1] = 1; ll ans = 0; for (int i=30; i>=0; --i) { for (int u=-1; u<=1; ++u) for (int v=-1; v<=1; ++v) for (int lw=0; lw<2; ++lw) { for (int lx=0; lx<2; ++lx) for (int ly=0; ly<2; ++ly) { ll &ret = dp[i+1][u+1][v+1][lw][lx][ly]; if (!ret) continue; int mx = lx?a>>i&1:1, my = ly?b>>i&1:1; for (int xx=0; xx<=mx; ++xx) for (int yy=0; yy<=my; ++yy) { if (lw&&(xx^yy)>(w>>i&1)) continue; int nu = u*2+xx-yy+(k>>i&1), nv = v*2+yy-xx+(k>>i&1); if (nu<-1||nv<-1) continue; nu = min(nu, 1), nv = min(nv, 1); if (!i) { if (nu>=0&&nv>=0) ans += ret; } else dp[i][nu+1][nv+1][lw&&(xx^yy)==(w>>i&1)][lx&&xx==mx][ly&&yy==my] += ret; } } } } printf("%lld ", ans); } }
M
可以得到$O(n^2)$的转移$f_{i,j}=(j+1)b_i f_{i-1,j+1}+c_i f_{i-1,j}$
就有$j! f_{n,j} = [x^j] sumlimits_{ige 0} i! a_i x^i prodlimits_{ige 2} (frac{b_i}{x}+c_i)=[x^{n-j}] sumlimits_{ige 0} i! a_i x^{n-i} prodlimits_{ige 2} (b_i x+c_i)$
可以用分治FFT求出