https://codeforces.com/contest/1794
C. Scoring Subsequences
分析：
发现每次前i个的最优答案一定是从后往前连乘的一段 分母依次可以考虑为1 2 3 4。。。(也就是n-i+1)
从后往前考虑
发现只要当前a[i]的>=n-i+1 对答案一定会造成贡献 因为分子/分母>=1
因为分子依次减小(或者不变) 分母依次增大 所以可以二分找到临界点
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
const int maxn=1e5+5;
#define ll long long
int n,mid,l,r;
int a[maxn];
void solve();
int main(){
int T;cin>>T;
while(T--)solve();
return 0;
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
l=1,r=i,mid=l+r>>1;
while(l<r){
mid=l+r>>1;
if(a[mid]>i-mid+1)r=mid-1;
else if(a[mid]==i-mid+1)l=r=mid;
else l=mid+1;
}
if(a[l]<i-l+1)l++;
printf("%d ",i-l+1);
}
printf("\n");
}
D. Counting Factorizations
分析
显然每个质数只能在底数中出现最多一次,在指数中可以出现多次.
设计dp状态 dp[i,j]表示已经处理了前i种数字 并且选择了j种数字作为底数
设前i种数字总共有sum个
考虑当前转移 数字x 有数量y个
如果x不是质数(只能当做指数) dp[i,j]+=dp[i-1,j]*C(n-(sum-j),y)
解释：需要将y个数字放入指数中 已经放了sum-j个指数(总共sum个数 有j个放底数 剩下的sum-j放指数) 总共有n个指数位置 所以C(n-(sum-j),y)
如果x是质数(可以当做指数) dp[i,j]+=dp[i-1,j-1]*C(n-(sum-(j-1)),y-1) 转移同理
代码细节 必须要预处理逆元 否则每次算的话是会超时的
但是有数字范围很大 怎么办 实际上逆元只需要处理阶乘的逆元即可 因为我们算的话只会用到阶乘的逆元
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5, mod = 998244353;
bool isPrime[maxn];
int primes[maxn], cnt;
ll jc[maxn],dp[maxn],ndp[maxn],ni[maxn];
map<int, int> mp;
map<int,int>::iterator it;
ll fast_mi(ll a ,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
void init(){
isPrime[1] = 1;
for(int i = 2; i < maxn; i++){
if (!isPrime[i]) primes[cnt++] = i;
for(int j = 0; i * primes[j] < maxn; j++){
isPrime[i * primes[j]] = 1;
if (i % primes[j] == 0) break;
}
}
jc[0]=1;ni[0]=1;
for(int i=1;i<maxn;i++)jc[i]=jc[i-1]*i%mod,ni[i]=fast_mi(jc[i],mod-2);
}
ll C(int n,int r){
return jc[n]*ni[r]%mod*ni[n-r]%mod;
}
int main(){
init();
int n;
cin >> n;
for(int i = 1; i <= 2 * n; i++){
int x;
cin >> x;
mp[x]++;
}
int sum = 0;
dp[0] = 1;
for(it=mp.begin();it!=mp.end();it++){
int val=it->first,num=it->second;
memset(ndp,0,sizeof(ndp));
for(int i = 0; i <= n; i++){
ndp[i] =(ndp[i]+ dp[i] * C(n - (sum - i), num)%mod)%mod;
if (i >= 1 && !isPrime[val]) ndp[i] =(ndp[i]+ dp[i - 1] * C(n - (sum - i + 1), num- 1)%mod)%mod;
}
for(int i=0;i<=n;i++)dp[i]=ndp[i];
sum += num;
}
cout << dp[n] << '\n';
}
E. Labeling the Tree with Distances
分析：
#include<iostream>
#include<cstring>
#include<random>
#include<map>
#include<set>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const int maxn = 2e5 + 5;
static const ULL mod = (1ull << 61) - 1;
ULL power[maxn];
mt19937_64 rnd(random_device{}());
uniform_int_distribution<ULL> dist(100, mod - 1);
const ULL base = dist(rnd);
static inline ULL add(ULL a, ULL b){
a += b;
if (a >= mod) a -= mod;
return a;
}
static inline ULL mul(ULL a, ULL b){
__uint128_t c = __uint128_t(a) * b;
return add(c >> 61, c & mod);
}
void init(){
power[0] = 1;
for(int i = 1; i < maxn; i++)
power[i] = mul(power[i - 1], base);
}
vector<int> g[maxn];
ULL f1[maxn], f2[maxn];
void dfs1(int u, int fa){
f1[u] = power[0];
for(auto j : g[u]){
if (j == fa) continue;
dfs1(j, u);
f1[u] = add(f1[u], mul(f1[j], base));
}
}
void dfs2(int u, int fa, ULL pre){
f2[u] = add(f1[u], mul(pre, base));
for(auto j : g[u]){
if (j == fa) continue;
dfs2(j, u, add(f2[u], mod - mul(f1[j], base)));
}
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
init();
int n;
cin >> n;
ULL hsh = 0;
for(int i = 0; i < n - 1; i++){
int x;
cin >> x;
hsh = add(hsh, power[x]);
}
for(int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs1(1, -1);
dfs2(1, -1, 0);
set<ULL> target;
for(int i = 0; i < n; i++)
target.insert(add(hsh, power[i]));
vector<int> ans;
for(int i = 1; i <= n; i++){
if (target.contains(f2[i])){
ans.push_back(i);
}
}
cout << ans.size() << '\n';
for(auto x : ans) cout << x << ' ';
cout << '\n';
}