因为本题卡空间
代码 #include<cstdio> const int maxn=1e7+5; const int mod=1e9+7; int ny[maxn],n,ans,sum; int main(){ scanf("%d",&n); ny[1]=1; for(int i=2;i<=n;i++){ ny[i]=1LL*(mod-mod/i)*ny[mod%i]%mod; } ans=0; for(int i=n-1;i>=1;i--){ ans=1LL*(sum+n-i+1LL)*ny[n-i]%mod; sum=(sum+ans)%mod; } printf("%d\n",ans); return 0; } 15、分手是祝愿 题目描述题目描述
分析其实这道题不是很难
但是题面往往具有迷惑性
我们可以发现每个按键都不可能被其他按键的组合键替代
于是我们实际上可以从大到小扫一遍，碰到亮的就按一遍，这样的话我们就可以找到所有必须要按的键
我们设 \(f[i]\) 为从第 \(i\) 个需要的键按到第 \(i-1\) 个需要的键期望按的次数
那么就有
\(f[i]=\frac{i}{n}+\frac{n-i}{n} \times (f[i]+f[i+1]+1)\)
移项化简就可以了
代码 #include<cstdio> #include<vector> const int maxn=1e5+5; const int mod=100003; inline int read(){ int x=0,fh=1; char ch=getchar(); while(ch<\'0\' || ch>\'9\'){ if(ch==\'-\') fh=-1; ch=getchar(); } while(ch>=\'0\' && ch<=\'9\'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*fh; } std::vector<int> g[maxn]; int n,a[maxn],f[maxn],ny[maxn],k; void pre(int now){ for(int i=1;i<=now;i++){ int mmax=now/i; for(int j=1;j<=mmax;j++){ g[i*j].push_back(i); } } } int main(){ n=read(),k=read(); for(int i=1;i<=n;i++){ a[i]=read(); } pre(n); ny[1]=1; for(int i=2;i<maxn;i++){ ny[i]=1LL*(mod-mod/i)*ny[mod%i]%mod; } int cs=0; for(int i=n;i>=1;i--){ if(a[i]==1){ for(int j=0;j<g[i].size();j++){ a[g[i][j]]^=1; } cs++; } } f[n]=0; for(int i=n;i>=1;i--){ f[i]=1LL*(n+1LL*(n-i)*f[i+1]%mod)%mod*ny[i]%mod; } int ans=0; if(k>=cs){ ans=cs; } else { for(int i=k+1;i<=cs;i++){ ans=(ans+f[i])%mod; } ans=(ans+k)%mod; } for(int i=1;i<=n;i++){ ans=1LL*ans*i%mod; } printf("%d\n",ans); return 0; }