1989: #6065. 「2017 山东一轮集训 Day3」第一题
题目描述
给定 n nn 根直的木棍，要从中选出 6 66 根木棍，满足：能用这 6 66 根木棍拼出一个正方形。注意木棍不能弯折。问方案数。
正方形：四条边都相等、四个角都是直角的四边形。
输入
第一行一个整数 n nn。
第二行包含 n nn 个整数 ai a_iai，代表每根木棍的长度。
输出
一行一个整数，代表方案数。
样例输入
8
4 5 1 5 1 9 4 5样例输出
3提示
对于 20% 20\%20% 的数据，n≤30 n \leq 30n≤30；
对于 40% 40\%40% 的数据，n≤200 n \leq 200n≤200；
对于 60% 60\%60% 的数据，n≤1000 n \leq 1000n≤1000；
对于 100% 100\%100% 的数据，n≤5000,1≤ai≤107 n \leq 5000, 1 \leq a_i \leq 10 ^ 7n≤5000,1≤ai≤107。
#include<cstdio>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=5005,S=1e7;
int n,a[N],sum[S+5],t[S+5],ans;
inline int C2(CI x)
{
return x*(x-1)/2LL;
}
inline int C3(CI x)
{
return x*(x-1)*(x-2)/6LL;
}
inline int C4(CI x)
{
return x*(x-1)*(x-2)*(x-3)/24LL;
}
signed main()
{
RI i,j; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]),++t[a[i]];
//1 1 1 3
for (sort(a+1,a+n+1),i=1;i<=n;++i)
{
for (j=i+1;j<=n;++j) if (t[a[j]]>=3) { ans+=sum[a[j]-a[i]]*C3(t[a[j]]); while (j<=n&&a[j]==a[j+1]) ++j; }
for (j=1;j<i;++j) if (a[i]+a[j]<=S) ++sum[a[i]+a[j]];
}
//1 1 2 2
for (n=unique(a+1,a+n+1)-a-1,i=1;i<=n;++i) if (t[a[i]]>=2)
{
int ret=0,cur=0; for (RI l=1,r=i-1;l<=r;++l)
{
while (l<=r&&a[l]+a[r]>a[i]) --r; if (l>r||a[l]+a[r]!=a[i]) continue;
if (l==r) { if (t[a[l]]>=4) ret+=C4(t[a[l]]); if (t[a[l]]>=2) ret+=C2(t[a[l]])*cur; } //important!
else { if (t[a[l]]>=2&&t[a[r]]>=2) ret+=C2(t[a[l]])*C2(t[a[r]]); ret+=t[a[l]]*t[a[r]]*cur; cur+=t[a[l]]*t[a[r]]; }
}
ans+=ret*C2(t[a[i]]);
}
return printf("%lld",ans),0;
}
1990: #6066. 「2017 山东一轮集训 Day3」第二题
题目描述
对于一棵有根树，定义一个点 u uu 的 k − 子树为 u uu 的子树中距离 u uu 不超过 k kk 的部分。注意，假如 u uu 的子树中不存在距离 u uu 为 k kk 的点，则 u uu 的 k − 子树是不存在的。
定义两棵子树是相同的，当且仅当不考虑点的标号时，他们的形态是相同的（儿子的顺序也需要考虑）。给定一棵 n nn 个点，点的标号在 [1,n] [1, n][1,n]，以 1 11 为根的有根树。问最大的 k kk，使得存在两个点 u≠v u \neq vu≠v，满足 u uu 的 k − 子树与 v vv 的 k − 子树相同。
输入
第一行输入一个正整数 n nn。
接下来读入 n nn 个部分，第 i ii 个部分描述点 i ii 的儿子，且以顺序给出。
每个部分首先读入一个整数 x xx，代表儿子个数。接下来 x xx 个整数，代表从左到右儿子的标号。
输出
输出一个整数 k kk，代表最大的合法的 k kk。
样例输入
8
1
2
2
3 4
0
1
5
2
6 7
0
1
8
0样例输出
3提示
对于 20% 20\%20% 的数据，n≤100 n \leq 100n≤100；
对于 40% 40\%40% 的数据，n≤2000 n \leq 2000n≤2000；
对于 60% 60\%60% 的数据，n≤30000 n \leq 30000n≤30000；
对于 100% 100\%100% 的数据，n≤100000 n \leq 100000n≤100000，保证给出的树是合法的。
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn(2e5 + 5);
const ull base(19260817);
unordered_map <ull, int> hash_table;
int first[maxn], cnt, n, idx, dfn[maxn], ed[maxn], mxd[maxn], st[maxn], top;
ull val[maxn], pw[maxn], hsh[maxn];
vector <int> son[maxn], kson[maxn];
inline void Dfs1(int u) {
dfn[u] = ++idx, val[idx] = 233;
for (auto v : son[u]) Dfs1(v), mxd[u] = max(mxd[u], mxd[v]);
ed[u] = ++idx, ++mxd[u], val[idx] = 131;
}
inline void Dfs2(int u, int k) {
st[++top] = u;
if (top - 1 > k) kson[st[top - k - 1]].push_back(u);
for (auto v : son[u]) Dfs2(v, k);
--top;
}
inline ull Hash(int l, int r) {
return hsh[r] - hsh[l - 1] * pw[r - l + 1];
}
inline int Calc(int k) {
register int i, l, r;
register ull v;
hash_table.clear();
for (i = 1; i <= n; ++i) kson[i].clear();
Dfs2(1, k);
for (i = 1; i <= n; ++i)
if (mxd[i] > k) {
l = dfn[i], v = 0;
for (auto to : kson[i]) {
r = dfn[to] - 1;
v = v * pw[r - l + 1] + Hash(l, r);
l = ed[to] + 1;
}
r = ed[i], v = v * pw[r - l + 1] + Hash(l, r);
if (hash_table.count(v)) return 1;
hash_table[v] = 1;
}
return 0;
}
int main() {
register int i, v, x, l, r, mid, ans;
scanf("%d", &n);
for (i = 1; i <= n; ++i)
for (scanf("%d", &x); x; --x) scanf("%d", &v), son[i].push_back(v);
Dfs1(1), pw[0] = 1;
for (i = 1; i <= idx; ++i) pw[i] = pw[i - 1] * base;
for (i = 1; i <= idx; ++i) hsh[i] = hsh[i - 1] * base + val[i];
l = 2, r = n, ans = 1;
while (l <= r) Calc(mid = (l + r) >> 1) ? ans = mid, l = mid + 1 : r = mid - 1;
printf("%d\n", ans);
return 0;
}
1991: #6067. 「2017 山东一轮集训 Day3」第三题
题目描述
给定 n,b,c,d,e n, b, c, d, en,b,c,d,e 以及 a0,a1,…an−1 a_0, a_1, \ldots a_{n - 1}a0,a1,…an−1，定义
xk=b×c4k+d×c2k+ef(x)=∑i=0n−1aixi
xkf(x)=b×c4k+d×c2k+e=∑i=0n−1aixi��=�×�4�+�×�2�+��(�)=∑�=0�−1����
xkf(x)=b×c4k+d×c2k+e=i=0∑n−1aixi
请你求出 f(x0),f(x1),⋯,f(xn−1) f(x_0), f(x_1), \cdots , f(x_{n - 1})f(x0),f(x1),⋯,f(xn−1) 对 106+3 10 ^ 6 + 3106+3 取模的值。
输入
第一行包括五个整数 n,b,c,d,e n, b, c, d, en,b,c,d,e。
接下来一行包括 n nn 个整数，代表 a0,a1,⋯,an−1 a_0, a_1, \cdots , a_{n - 1}a0,a1,⋯,an−1。
输出
n nn 行，第 i ii 行代表 f(xi−1) f(x_{i - 1})f(xi−1)。
样例输入
3 1 2 3 4
0 1 2样例输出
136
2080
190036提示
| 测试点编号 | n≤ n \leqn≤ | 特殊条件 |
|---|---|---|
| 1 | 500 500500 | |
| 2 | 2000 20002000 | |
| 3 | 10000 1000010000 | |
| 4 | 20000 2000020000 | |
| 5 | 30000 3000030000 | |
| 6 | 40000 4000040000 | |
| 7 | 50000 5000050000 | b=0 b = 0b=0 |
| 8 | 60000 6000060000 | b=0 b = 0b=0 |
| 9 | 60000 6000060000 | |
| 10 | 60000 6000060000 |
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<functional>
#include<cmath>
#include<vector>
#include<assert.h>
//using namespace std;
using std::min;
using std::max;
using std::swap;
using std::sort;
using std::reverse;
using std::random_shuffle;
using std::lower_bound;
using std::upper_bound;
using std::unique;
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
void open(const char *s){
#ifndef ONLINE_JUDGE
char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}
void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}
int upmin(int &a,int b){if(b<a){a=b;return 1;}return 0;}
int upmax(int &a,int b){if(b>a){a=b;return 1;}return 0;}
const ll p=1000003;
const int N=530000;
ll fp(ll a,ll b)
{
if(!b)
return 1;
b=(b%(p-1)+p-1)%(p-1);
ll s=1;
for(;b;b>>=1,a=a*a%p)
if(b&1)
s=s*a%p;
return s;
}
namespace fft
{
const int W=524288;
const ll M=1000;
typedef double db;
db pi=acos(-1);
struct cp
{
db x,y;
cp(db a=0,db b=0):x(a),y(b){}
};
cp operator +(cp a,cp b){return cp(a.x+b.x,a.y+b.y);}
cp operator -(cp a,cp b){return cp(a.x-b.x,a.y-b.y);}
cp operator *(cp a,cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
cp operator /(cp a,int b){return cp(a.x/b,a.y/b);}
cp conj(cp a){return cp(a.x,-a.y);}
cp muli(cp a){return cp(-a.y,a.x);}
cp divi(cp a){return cp(a.y,-a.x);}
int rev[N];
cp *w[20];
void fft(cp *a,int n,int t)
{
for(int i=1;i<n;i++)
{
rev[i]=(rev[i>>1]>>1)|(i&1?n>>1:0);
if(rev[i]>i)
swap(a[rev[i]],a[i]);
}
for(int i=2,s=1;i<=n;i<<=1,s++)
for(int j=0;j<n;j+=i)
for(int k=0;k<i/2;k++)
{
cp u=a[j+k];
cp v=a[j+k+i/2]*w[s][k];
a[j+k]=u+v;
a[j+k+i/2]=u-v;
}
if(t==-1)
{
reverse(a+1,a+n);
for(int i=0;i<n;i++)
a[i]=a[i]/n;
}
}
void dft(db *a,db *b,cp *c,cp *d,int n)
{
static cp a1[N],a2[N];
for(int i=0;i<n;i++)
a1[i]=cp(a[i],b[i]);
fft(a1,n,1);
for(int i=0;i<n;i++)
a2[i]=conj(a1[i]);
reverse(a2+1,a2+n);
for(int i=0;i<n;i++)
{
c[i]=(a1[i]+a2[i])/2;
d[i]=divi(a1[i]-a2[i])/2;
}
}
void idft(db *a,db *b,cp *c,cp *d,int n)
{
static cp a1[N];
for(int i=0;i<n;i++)
a1[i]=c[i]+muli(d[i]);
fft(a1,n,-1);
for(int i=0;i<n;i++)
{
a[i]=a1[i].x;
b[i]=a1[i].y;
}
}
void init()
{
for(int i=1;i<=19;i++)
w[i]=new cp[1<<(i-1)];
for(int i=0;i<W/2;i++)
w[19][i]=cp(cos(2*pi/W*i),sin(2*pi/W*i));
for(int i=18;i>=1;i--)
for(int j=0;j<1<<(i-1);j++)
w[i][j]=w[i+1][j<<1];
}
void mul(ll *a,ll *b,ll *c,int n,int m,int l)
{
static db a1[N],a2[N],b1[N],b2[N],c1[N],c2[N],d1[N],d2[N];
static cp a3[N],a4[N],b3[N],b4[N],c3[N],c4[N],d3[N],d4[N];
int k=1;
while(k<=n+m)
k<<=1;
for(int i=0;i<k;i++)
a1[i]=a2[i]=b1[i]=b2[i]=0;
for(int i=0;i<=n;i++)
{
a[i]=(a[i]+p)%p;
a1[i]=a[i]/M;
a2[i]=a[i]%M;
}
for(int i=0;i<=m;i++)
{
b[i]=(b[i]+p)%p;
b1[i]=b[i]/M;
b2[i]=b[i]%M;
}
dft(a1,a2,a3,a4,k);
dft(b1,b2,b3,b4,k);
for(int i=0;i<k;i++)
{
c3[i]=a3[i]*b3[i];
c4[i]=a3[i]*b4[i];
d3[i]=a4[i]*b3[i];
d4[i]=a4[i]*b4[i];
}
idft(c1,c2,c3,c4,k);
idft(d1,d2,d3,d4,k);
for(int i=0;i<=l;i++)
c[i]=((ll)(c1[i]+0.5)%p*M%p*M%p+(ll)(c2[i]+0.5)%p*M%p+(ll)(d1[i]+0.5)%p*M%p+(ll)(d2[i]+0.5)%p)%p;
}
}
int n;
ll B,C,D,E;
ll a[N];
ll inv[N],fac[N],ifac[N];
void init()
{
inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
for(int i=2;i<=200000;i++)
{
inv[i]=-p/i*inv[p%i]%p;
inv[i]=(inv[i]+p)%p;
fac[i]=fac[i-1]*i%p;
ifac[i]=ifac[i-1]*inv[i]%p;
}
}
namespace pregao
{
ll b[N],c[N],s[N];
void gao()
{
for(int i=0;i<n;i++)
{
b[i]=a[n-i-1]*fac[n-i-1]%p;
c[i]=ifac[i]*fp(E,i)%p;
}
fft::mul(b,c,s,n-1,n-1,n-1);
reverse(s,s+n);
}
}
namespace gao1
{
ll d[N],e[N],f[N],g[N],h[N],ans[N];
void gao()
{
pregao::gao();
for(int i=0;i<n;i++)
{
d[i]=pregao::s[i]*fp(D,i)%p*fp(C,(ll)i*i)%p*ifac[i]%p;
e[i]=fp(C,-(ll)i*i);
}
fft::mul(d,e,f,n-1,n-1,n-1);
reverse(d,d+n);
e[0]=0;
fft::mul(d,e,g,n-1,n-1,n-1);
for(int i=0;i<n;i++)
{
ans[i]=((f[i]+g[n-i-1])%p+p)%p;
ans[i]=ans[i]*fp(C,(ll)i*i)%p;
}
for(int i=0;i<n;i++)
printf("%lld\n",ans[i]);
}
}
namespace gao2
{
ll b[N],c[N],d[N],e[N],f[N],g[N],ans[N];
void gao()
{
E=(E-D*D%p*fp(4*B,p-2)%p+p)%p;
D=D*fp(2*B,p-2)%p;
pregao::gao();
for(int i=0;i<n;i++)
b[2*n-2*i-2]=fac[2*i]*ifac[i]%p*pregao::s[i]%p*fp(B,i)%p;
for(int i=0;i<2*n-1;i++)
c[i]=fp(D,i)*ifac[i]%p;
fft::mul(b,c,d,2*n-2,2*n-2,2*n-2);
reverse(d,d+2*n-1);
for(int i=0;i<2*n-1;i++)
{
d[i]=d[i]*ifac[i]%p*fp(C,(ll)i*i)%p;
e[i]=fp(C,-(ll)i*i);
}
fft::mul(d,e,f,n-1,n-1,n-1);
reverse(d,d+2*n-1);
e[0]=0;
fft::mul(d,e,g,2*n-2,2*n-2,2*n-2);
for(int i=0;i<n;i++)
ans[i]=(fp(C,(ll)i*i)*(f[i]+g[2*n-i-2])%p+p)%p;
for(int i=0;i<n;i++)
printf("%lld\n",ans[i]);
}
}
namespace gao0
{
void gao()
{
ll ans=0;
for(int i=n-1;i>=0;i--)
{
ans=ans*(E+B+D)%p;
ans=(ans+a[i])%p;
}
printf("%lld\n",ans);
ans=0;
for(int i=n-1;i>=0;i--)
{
ans=ans*E%p;
ans=(ans+a[i])%p;
}
for(int i=1;i<n;i++)
printf("%lld\n",ans);
}
}
int main()
{
open("loj6067");
fft::init();
init();
scanf("%d%lld%lld%lld%lld",&n,&B,&C,&D,&E);
for(int i=0;i<n;i++)
a[i]=rd();
if(!C)
gao0::gao();
else if(!B)
gao1::gao();
else
gao2::gao();
return 0;
}
