刚刚发现vscode的copilot free在帮我半自动过题。吓哭了。

A - CF1422C Bargain

Rating：1700.

给出数字串 \(n\)（长度 \(\le10^5\)），对所有区间 \([l,r]\)，累加删去 \([l,r]\) 后得到的数字，对 \(1e9+7\) 取模。

即求

\[\sum_{l=1}^{n}\sum_{r=l}^{n}s(1,l-1)\cdot10^{n-r}+s(r+1,n) \]

很简单。

点击查看代码
#include
#define ll long long
#define N 100010
#define P 1000000007
using namespace std;
string s;
int n,a[N];
ll pre[N],suf[N],pw[N];
ll spw[N];
int main(){cin>>s;getchar();n=s.size(),pw[0]=1;for(int i=1;i<=n;i++){a[i]=s[i-1]-48;pw[i]=10ll*pw[i-1]%P;}for(int i=1;i<=n;i++)pre[i]=(10ll*pre[i-1]+a[i])%P;for(int i=n;i;i--){suf[i]=(a[i]*pw[n-i]+suf[i+1])%P;spw[i]=(pw[n-i]+spw[i+1])%P;}ll ans=0;for(int l=2;l<=n;l++)(ans+=pre[l-1]*spw[l]%P)%=P;for(int r=1;r
B - CF148D Bag of mice

Rating：1800.

A 和 B 玩游戏。袋子中有 \(w\) 只白鼠，\(b\) 只黑鼠，两人轮流摸出一只老鼠，先摸到白鼠者胜。

但是当 B 摸完后，袋子中若仍有老鼠，其中会随机逃跑一只老鼠（等概率）。

求 A 的胜率。\(1\le w,b\le 1000\)。

只需注意到两人胜率之和大概率不为 1，不过应该认真读完题就能明白。

故递归一个 \(f[w][b]\) 的 dp，注意边界即可。

点击查看代码
#include
#define db double
#define N 1010
using namespace std;
int read(){int x=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*w;
}
db f[N][N];
db bord(int w,int b){if(!w)return 0;if(!b)return 1;if(w==1&&b==1)return 1.0/2;if(w==1&&b==2)return 1.0/3;if(w==2&&b==1)return 2.0/3;return -1;
}
db calc(int w,int b){if(w<0||b<0)return 0;if(w+b<=3)return bord(w,b);if(f[w][b])return f[w][b];db tmp=1.0*w/(w+(b-2))*calc(w-1,b-2)+1.0*(b-2)/(w+(b-2))*calc(w,b-3);// printf("w b tmp %d %d %.5lf\n",w,b,tmp);return f[w][b]=1.0*w/(w+b)+1.0*b/(w+b)*(b-1)/(w+(b-1))*tmp;
}
int main(){int w=read(),b=read();printf("%.10lf\n",calc(w,b));return 0;
}
C - CF1207D Number Of Permutations

Rating：1800.

给定 \(n\) 个二元组 \((a_i,b_i)\)，问它们的 \(n!\) 个排列中有多少满足：

  • \(\{a_n\}\) 和 \(\{b_n\}\) 均是非不降的。

\(n\le 3e5\)，模大质数。

copilot 神力吓到我了。此题是简单容斥。

点击查看代码
#include
#define N 300010
#define P 998244353
using namespace std;
int read(){int x=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*w;
}
struct dat{int a,b;
}d[N];
bool cmpa(dat x,dat y){if(x.a!=y.a)return x.a
D - CF1366D Two Divisors

给定 \(a\)，找到其非 \(1\) 的因数 \(b,c\) 使得 \(\gcd(b+c,a)=1\).

\(T\le 5\times 10^5\)，\(a\le 10^7\)。

Rating：2000，有点超乎我的想象。

若 \(a=1\) 或 \(a=p^k\)，显然不行。

否则设 \(a=p_1^{c_1}\cdot res\)，令答案为 \(p_1\) 和 \(res\) 即可。