B
先选出n-1种颜色C(n,n-1)=n
剩下的就是n-1个不同的数放n个位置
然后从n-1种颜色种选择一个作为重复的颜色 C(n-1,1)=n-1
在从n个位置选择两个放重复颜色，C(n,2)
最后n-2个位置为(n-2)!
整理：
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 1e6 + 4;
const int N = 5e3 + 5;
const double eps = 1e-6;
const double pi = acos(-1.0);
ll qpow(ll x,ll y){ll ans=1;x%=mod;assert(y>=0);while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}
//#define LOCAL
int _,n,m,k,a[maxn];
ll f[maxn];
int main() {
#ifdef LOCAL
freopen("RACE input.in","r",stdin);
#endif
f[0]=1;
for(int i=1;i<=1e6;i++) f[i]=f[i-1]*i%mod;
while(~scanf("%d",&n)) {
if(n==1) printf("0\n");
else
printf("%lld\n",(n-1)*(n-1)%mod*n%mod*n%mod*f[n-2]%mod*qpow(2,mod-2)%mod);
}
}
C
n<=3时无解否则
AAR{AAAAA(n-4个)}R
AR数量为2+(n-4+2)=n,长度3+n-4+1=n
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int maxn = 2e6 + 4;
const int N = 5e3 + 5;
const double eps = 1e-6;
const double pi = acos(-1.0);
ll qpow(ll x,ll y,ll mod){ll ans=1;x%=mod;assert(y>=0);while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}
//#define LOCAL
int n,a[maxn];
int main() {
#ifdef LOCAL
freopen("RACE input.in","r",stdin);
#endif
while(~scanf("%d",&n)) {
if(n<=3) printf("-1\n");
else {
printf("AAR");
for(int i=1;i<=n-4;i++) printf("A");
printf("R\n");
}
}
}D
看清题意，要求的是用尽可能多的方式走到n,m。所以我们直接二进制枚举用哪些方式走，记忆化搜索看能否 走到即可
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 1e6 + 4;
const int N = 100 + 5;
const double eps = 1e-6;
const double pi = acos(-1.0);
ll qpow(ll x,ll y){ll ans=1;x%=mod;assert(y>=0);while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}
//#define LOCAL
int _,n,m,k;
char s[maxn];
int dp[N][N][33];
struct node{int x,y ;}a[maxn];
int dfs(int n,int m,int S,int used) {
if(n==0&&m==0) {return S==used; }
if(dp[n][m][used]!=-1) return dp[n][m][used];
int ans=0;
for(int i=0;i<k;i++) {
if(S&(1<<i)) {
int xx=n-a[i].x,yy=m-a[i].y;
if(xx>=0&&yy>=0) ans|=(dfs(xx,yy,S,used|(1<<i)));
}
}
return dp[n][m][used]=ans;
}
int cnt(int S) {
int ans=0;
while(S) ans+=S%2,S/=2;
return ans;
}
int main() {
#ifdef LOCAL
freopen("RACE input.in","r",stdin);
#endif
for(scanf("%d",&_);_;_--) {///
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<k;i++) {
scanf("%s",s+1);
int len=strlen(s+1),x=0,y=0;
for(int j=1;j<=len;j++) {
if(s[j]=='U') y++;
if(s[j]=='R') x++;
}
a[i]={x,y};
}
int limit=1<<k,ans=0;
for(int S=0;S<limit;S++) {
memset(dp,-1,sizeof dp);
if(dfs(n,m,S,0)) ans=max(ans,cnt(S));
}
printf("%d\n",ans);
}
}
两个数的LCM就相当于将这两个数拆成 p1^k1*p2^k2...形式后每个素因子对应的k取max
那么如果我们想要LCM最大，把所有数都选是最优的方法之一
预处理后暴力即可
E
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+9;
const int maxn = 2e6 + 4;
const int N = 5e3 + 5;
const double eps = 1e-6;
const double pi = acos(-1.0);
ll qpow(ll x,ll y){ll ans=1;x%=mod;assert(y>=0);while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}
//#define LOCAL
int vis[maxn],a[maxn],cnt[maxn],mx[maxn];
VI v[maxn];
int main() {
#ifdef LOCAL
freopen("RACE input.in","r",stdin);
#endif
for(int i=2;i<=1e5;i++) {
if(vis[i]) continue;
v[i].pb(i);
for(int j=i+i;j<=1e5;j+=i) v[j].pb(i),vis[j]=1;
}
// for(int i=10;i<=50;i++) {
// printf("%d:",i);
// for(int j:v[i]) printf("%d ",j);printf("\n");
// }
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);int d=a[i];
for(int j:v[a[i]]) while(d%j==0) d/=j,cnt[j]++;
for(int j:v[a[i]]) mx[j]=max(mx[j],cnt[j]);
for(int j:v[a[i]]) cnt[j]=0;
}
ll ans=1;
for(int i=1;i<=1e5;i++) {
ans=ans*qpow(i,mx[i])%mod;
}
printf("%lld\n",ans);
}F
先考虑如果配对，可以发现，当某颗子树存在某种颜色的权值>这颗子树总权值/2时那么配对数为总权值-该颜色权值，否则为总权值/2.
又因为查询的是所有子树的配对数，所以我们可以通过dfs序将子树问题转化为区间问题
那么问题就是对于各个子树区间，求某种颜色的最大权值。主席树模拟即可
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2e5 + 4;
const int N = 5e3 + 5;
const double eps = 1e-6;
const double pi = acos(-1.0);
ll qpow(ll x,ll y){ll ans=1;x%=mod;assert(y>=0);while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}
//#define LOCAL
int dfn[maxn],sz[maxn],seq[maxn],col[maxn],cnt[maxn],tot,n;
VI G[maxn];
void dfs(int u,int fa) {
dfn[u]=++tot;sz[u]=1;seq[tot]=u;
for(int v:G[u]) if(v!=fa) dfs(v,u),sz[u]+=sz[v];
}
struct node { int l,r,sum;}T[maxn*25];
int root[maxn*25],sum[maxn];
void update(int l,int r,int &x,int y,int pos,int num) {
T[++tot]=T[y];T[tot].sum+=num;x=tot;
if(l==r) return ;
int mid=l+r>>1;
if(mid>=pos) update(l,mid,T[x].l,T[y].l,pos,num);
else update(mid+1,r,T[x].r,T[y].r,pos,num);
}
int ask(int l,int r,int x,int y,int k) {
if(l==r) return l;
int mid=l+r>>1;
if((T[T[y].l].sum-T[T[x].l].sum)*2>k) return ask(l,mid,T[x].l,T[y].l,k);
if((T[T[y].r].sum-T[T[x].r].sum)*2>k) return ask(mid+1,r,T[x].r,T[y].r,k);
return 0;
}
int ask1(int l,int r,int x,int y,int pos) {
if(l==r) return T[y].sum-T[x].sum;
int mid=l+r>>1;
if(pos<=mid) return ask1(l,mid,T[x].l,T[y].l,pos);
else return ask1(mid+1,r,T[x].r,T[y].r,pos);
}
int main() {
#ifdef LOCAL
freopen("RACE input.in","r",stdin);
#endif
scanf("%d",&n);
for(int i=1;i<n;i++) {
int u,v;scanf("%d%d",&u,&v);
G[u].pb(v);G[v].pb(u);
}
for(int i=1;i<=n;i++) scanf("%d%d",&col[i],&cnt[i]);
dfs(1,-1);tot=0;
for(int i=1;i<=n;i++) {
update(1,2e5,root[i],root[i-1],col[seq[i]],cnt[seq[i]]);
sum[i]=sum[i-1]+cnt[seq[i]];
}
for(int i=1;i<=n;i++) {
int l=dfn[i],r=dfn[i]+sz[i]-1;
int z=ask(1,2e5,root[l-1],root[r],sum[r]-sum[l-1]);
//cout<<z<<','<<l<<','<<r<<','<<sum[r]-sum[l-1]<<',';
if(!z) z=(sum[r]-sum[l-1])/2;
else z=sum[r]-sum[l-1]-ask1(1,2e5,root[l-1],root[r],z);
printf("%d\n",z);
}
}
京公网安备 11010502036488号