洛谷3672：小清新签到题—

洛谷3672：小清新签到题——题解

阅读量：5975 次

发布时间：2019-06-20

本文共 1481 字，大约阅读时间需要 4 分钟。

题目见上面。

参考：

讲真我最开始真不知道求方案数有什么用。

f[i][j]表示i个数j个逆序对有多少种方案。

显然我们有f[i][j]=f[i-1][j]+f[i-1][j-1]+……+f[i-1][j-i+1]

（就相当于给一个比序列中所有数都大的数，让你往里插。）

于是令s[i][j]为前缀和，优化成f[i][j]=s[i-1][j]-s[i-1][j-i]。

同时注意f数组可能爆longlong，但是因为k<=1e13所以没必要那么多方案，当f[i][j]>k的时候统一换成INF就行。

然后我们枚举每一位可以放什么数，统计放这个数所造成的贡献c，以及之前可以放的数（但因为达不到k而被放弃）的方案数tmp。

则当f[i-1][x-c]+tmp>=k的时候就可以放这个数了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;const int N=305;inline ll read(){ ll X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}int ans[N],vis[N];ll f[N][N*N/2],s[N][N*N/2];int main(){ int n=read();ll k=read();int x=read(); f[0][0]=1; for(int i=0;i<=x;i++)s[0][i]=1; for(int i=1;i<=n;i++){ for(int j=0;j<=x;j++){ int l=max(0,j-i+1),r=j; ll tmp=(!l)?s[i-1][r]:s[i-1][r]-s[i-1][l-1]; f[i][j]=min(tmp,k+1); s[i][j]=f[i][j]+(j?s[i][j-1]:0); } } for(int i=n;i>=1;i--){ ll tmp=0; for(int j=1;j<=n;j++){ if(!vis[j]){ int c=j-1; for(int l=1;l
             
              =k){ ans[n-i+1]=j;vis[j]=1; x-=c;k-=tmp;break; } tmp+=f[i-1][x-c]; } } } for(int i=1;i<=n;i++)printf("%d ",ans[i]); puts(""); return 0;}