Multi school sprint noip 10.29
Am I blind? And then led me to successfully cut off the last question and change my life?
\(JKlover \) the question is still conscience. At least it's for the big example
As for my second kind of Stirling number, I just spent two hours on the first question. This is a serious strategic mistake
This time I saw that each question had a little clue
However, the depth of thinking is deep, and the meaning of the question needs to be constantly transformed
A good set of questions to exercise the ability of thinking and optimizing algorithms
However, there is only explosive search, and there is no violence that can be taken
T1 berry conscience
The idea in my examination room is troublesome. I decide who is the first one, and then enumerate the following schemes
In the process, multiply the number in each set, so as to calculate how many times each number should be added
Finally, multiply the sum of the weights directly
SB_code#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=2e3+5;
const int mod=998244353;
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;y>>=1;
}return ret;
}
int n,k,dp[N][N],ans;
int w[N],sum;
int jc[N],inv[N];
int C(int x,int y){return jc[x]*inv[y]%mod*inv[x-y]%mod;}
signed main(){
freopen("ichigo.in","r",stdin);
freopen("ichigo.out","w",stdout);
scanf("%lld%lld",&n,&k);
fo(i,1,n)scanf("%lld",&w[i]),sum=(sum+w[i])%mod;
jc[0]=1;fo(i,1,n)jc[i]=jc[i-1]*i%mod;
inv[0]=1;inv[n]=ksm(jc[n],mod-2);
fu(i,n-1,1)inv[i]=inv[i+1]*(i+1)%mod;
dp[0][0]=1;
fo(i,1,n)fo(j,1,min(n,k))dp[i][j]=(dp[i][j]+dp[i-1][j-1]+dp[i-1][j]*j%mod)%mod;
fo(i,1,n-k+1)ans=(ans+i*C(n-1,i-1)%mod*dp[n-i][k-1])%mod;
ans=ans*sum%mod;
printf("%lld",ans);
return 0;
}
The recurrence (dp) I wrote in the examination room seems to be the recurrence of the second kind of Stirling number
However, if we use the formula written by my examination room mountain, even the inclusion exclusion method of the second kind of Stirling number can not be cut off
The real idea is that if two numbers appear in the same set, their weights will be added
In this way, it is solved with two Stirling numbers, which can be obtained in the time of \ (\ mathcal{O(nlogn)} \) and \ (\ mathcal{O(n)} \)
AC_code#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=1e6+5;
const int mod=998244353;
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;y>>=1;
}return ret;
}
int n,k,ans,res1,res2;
int p[N],cnt,pw[N];
bool vis[N];
int w[N],sum,mi[N];
int jc[N],inv[N];
int C(int x,int y){return jc[x]*inv[y]%mod*inv[x-y]%mod;}
signed main(){
freopen("ichigo.in","r",stdin);
freopen("ichigo.out","w",stdout);
scanf("%lld%lld",&n,&k);
fo(i,1,n)scanf("%lld",&w[i]),sum=(sum+w[i])%mod;
jc[0]=1;fo(i,1,n)jc[i]=jc[i-1]*i%mod;
inv[0]=1;inv[n]=ksm(jc[n],mod-2);
fu(i,n-1,1)inv[i]=inv[i+1]*(i+1)%mod;
pw[1]=1;fo(i,2,n){
if(!vis[i])p[++cnt]=i,pw[i]=ksm(i,n-1);
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
pw[i*p[j]]=pw[i]*pw[p[j]]%mod;
vis[i*p[j]]=true;
if(i%p[j]==0)break;
}
}
int bas=1;fo(i,0,k){res2=(res2+C(k,i)*pw[k-i]%mod*bas+mod)%mod;bas=-bas;}res2=res2*inv[k]%mod;
bas=1;fo(i,0,k){res1=(res1+C(k,i)*pw[k-i]%mod*(k-i)%mod*bas+mod)%mod;bas=-bas;}res1=res1*inv[k]%mod;
ans=(res1+(n-1)*res2)%mod;
ans=ans*sum%mod;
printf("%lld",ans);
return 0;
}
I've run out of pears
Seriously, I don't have any ideas on this question in the examination room
Although I think of the sorting method, I can't get through one of the data after I arrange it and look from front to back
Then my mind broke and I went straight to die, okay
Later, after the test, I found that the sorting method was right, but I couldn't choose along
This ranking just tells you that I have selected the store collection in this order
Next, you can \ (DP \). Let \ (dp_{i,j} \) represent the minimum time for the first \ (I \) stores to go to \ (j \)
Just transfer directly. It seems that the complexity is not very good
But for one thing, the increase of time is exponential, so the upper bound of \ (j \) is \ (log \)
In this way, the complexity reaches the \ (log \) level, but you find that the exponential level is for the case where \ (a \) is not equal to \ (0 \)
So the last \ (0 \) is sorted from large to small according to \ (b \), and you can add as much as you can
AC_code#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=2e5+5;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,T;
struct node {
int a,b;
node(){}
bool operator < (node x)const{
return x.a*(b+1)<a*(x.b+1);
}
}sca[N];
int ans,now=1;
int f[N][35];
bool com(node x,node y){return x.b<y.b;}
signed main(){
freopen("eriri.in","r",stdin);
freopen("eriri.out","w",stdout);
scanf("%lld%lld",&n,&T);
fo(i,1,n)scanf("%lld%lld",&sca[i].a,&sca[i].b);
sort(sca+1,sca+n+1);
memset(f,0x3f,sizeof(f));
int pos=n+1;
fo(i,0,n)f[i][0]=0;
fo(i,1,n){
if(!sca[i].a){pos=i;break;}
fo(j,1,min(i,30ll))f[i][j]=f[i-1][j];
fo(j,1,min(i,30ll)){
if(f[i-1][j-1]==inf)continue;
if(f[i-1][j-1]+1+(f[i-1][j-1]+1)*sca[i].a+sca[i].b<=T)
f[i][j]=min(f[i][j],f[i-1][j-1]+1+(f[i-1][j-1]+1)*sca[i].a+sca[i].b);
}
}
fo(i,0,min(pos-1,30ll))if(f[pos-1][i]<=T)ans=max(ans,i);
int sum=0;
sort(sca+pos,sca+n+1,com);
fo(i,pos,n){
sum+=sca[i].b+1;
fo(j,1,min(pos-1,30ll)){
if(sum+f[pos-1][j]<=T)ans=max(ans,j+i-pos+1);//cout<<j<<" "<<i<<" "<<pos<<" "<<j+i-pos+1<<endl;
}
}
printf("%lld",ans);
}
T3 regiment, but
Only \ (10min \) is left when looking at this question
Then I searched and left. In fact, this question has been very kind
It can be solved by recursion, which is not as difficult as we think
Please look at the solution... I'm cooing
AC_code#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=1e7+5;
const int mod=1e9+7;
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;y>>=1;
}return ret;
}
int n,ans;
int pw[N],p[N];
int f[N];
signed main(){
freopen("yui.in","r",stdin);
freopen("yui.out","w",stdout);
scanf("%lld",&n);
pw[0]=1;fo(i,1,n)pw[i]=pw[i-1]*2%mod;
p[0]=1;fo(i,1,n)p[i]=p[i-1]*((pw[n]-i+mod)%mod)%mod;
f[1]=f[2]=0;
fo(i,3,n)f[i]=(p[i-1]-f[i-1]-(i-1)*(pw[n]-i+1)%mod*f[i-2]%mod+mod+mod)%mod;
printf("%lld",(p[n]-f[n]+mod)%mod);
return 0;
}
T4 seven negative me
This time I can cut off this question in the examination room, which completely depends on my hand. I took this as the second question
Then think it's very simple and very confident \ (meet\ in\ the\ middle \)
The conclusion is that complete graphs contribute the most
So we just need to find the largest complete subgraph in this graph
First find the first half, then find the second half, and merge directly!!!!!
AC_code#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=41;
int n,m,l,r,ul,ur;
int e[N][2],mx;
int sum[1<<20],ys[1<<20],rit[1<<20];
bool vis[1<<20];
double x,ans;
signed main(){
freopen("nanami.in","r",stdin);
freopen("nanami.out","w",stdout);
scanf("%d%d%lf",&n,&m,&x);
l=n>>1;ul=(1<<l)-1;
r=n-l;ur=(1<<r)-1;
fo(i,1,m){
int x,y;
scanf("%d%d",&x,&y);
if(y>l)e[x][1]|=(1<<y-l-1);
else e[x][0]|=(1<<y-1);
if(x>l)e[y][1]|=(1<<x-l-1);
else e[y][0]|=(1<<x-1);
}
fo(i,1,l)e[i][0]|=(1<<i-1);
fo(i,1,r)e[i+l][1]|=(1<<i-1);
fo(i,1,max(ul,ur))sum[i]=sum[i-(i&-i)]+1;
fo(s,1,ul){
int now,num=sum[s],rig=ur;
bool flag=true;
fo(i,1,l){
if(!((s>>i-1)&1))continue;
now=e[i][0]&s;rig&=e[i][1];
if(sum[now]!=num){flag=false;break;}
}
if(flag){
mx=max(mx,num);
ys[s]=rig;
}
}
fo(s,1,ur){
int now,num=sum[s];
bool flag=true;
fo(i,1,r){
if(!((s>>i-1)&1))continue;
now=e[i+l][1]&s;
if(sum[now]!=num){flag=false;break;}
}
if(flag){
mx=max(mx,num);
vis[s]=true;
}
}
memset(rit,-1,sizeof(rit));
fu(s,ul,1){
if(!ys[s]||sum[s]+sum[ys[s]]<mx)continue;
if(rit[ys[s]]!=-1){mx=max(mx,sum[s]+rit[ys[s]]);continue;}
int now=0;
for(int t=ys[s];t;t=(t-1)&ys[s]){
if(vis[t])now=max(now,sum[t]);
}
rit[ys[s]]=now;
mx=max(mx,sum[s]+now);
}
ans=1.0*mx*(mx-1)/2.0;
ans=ans*(1.0/(1.0*mx*mx))*x*x;
printf("%.6lf",ans);
return 0;
}