[杭电春季联赛5]1004 赛马

原帖地址https://www.cnblogs.com/Reisentyan/p/19885859[杭电春季联赛5]1004 赛马我们将使用拉马努金瞪眼法解决这一题注意到样例很有规律考虑找规律当rxrxrx时对答案有多少贡献手玩枚举发现r (十进制)贡献1021314353647487确实很有规律注意到题面中存在logloglog发现与二进制相关于是将rrr转换成二进制r (二进制)贡献0001000101001110100301013011040111410007此时答案已经很清晰了我们发现当末尾突然多出几个后缀零做出的贡献就多出同样的数量并且我们发现做出的贡献等于r−popcount(r)r - \text{popcount}(r)r−popcount(r)也就是说111到nnn求和减去所有的二进制位111的数量 ansansans$ \sum_{i1}^{n} i - \sum_{i1}^{n} \text{popcount}(i) \text{ans} $​二进制位111的数量可以用数位DP算出注意到代码要写成这样void solve() { ll n q_; ll all (n 1) * n / 2; constexpr int N 64; ll l, r, dp[N], mi[N]; ll ans1[2] { 0 }, ans2[N] { 0 }; int a[N]; auto gett [](ll nn, ll* ans)-void { ll tmp nn; int len 0; while (nn) a[len] nn % 2, nn / 2; for (int i len; i 1; --i) { for (int j 0; j 2; j) ans[j] dp[i - 1] * a[i]; for (int j 0; j a[i]; j) ans[j] mi[i - 1]; tmp - mi[i - 1] * a[i], ans[a[i]] tmp 1; ans[0] - mi[i - 1]; }; }; l 1; r n; mi[0] 1ll; dp[0] 0; for (int i 1; i 62; i) { dp[i] dp[i - 1] * 2 mi[i - 1]; mi[i] 2ll * mi[i - 1]; } gett(r, ans1), gett(l - 1, ans2); cout all - ans1[1] ans2[1] endl; return; } /* ⡀⠎⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣄⠃⠈⣶⡛⠿⠭⣉⠛⠿⡿⠛⠉⣀⣠⣤⣭⡏⠴⢀⣴⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿ ⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣷⣱⣬⠛⠉⠀⠀⢠⠀⠀⠀⢀⣀⠀⠉⠿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠈⡿ ⠀⠀⠀⠀⠀⠀⠀⢀⢿⣿⣿⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⡏⠀⠀⠀⠀⠈⠳⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⠋⠀⣇⠀⠀⠀⠀⠀⠀⠀⠀⠈ ⠀⠀⠀⠀⠀⠀⠀⣸⠀⣿⣿⣿⣿⠟⠀⠀⠀⠂⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠈⡀⠀⠀⠀⠻⣿⣿⣿⣿⣷⡀⠘ ⠀⠀⠀⠀⠀⠀⠀⣧⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠙⣿⣿⣿⣿⣿⣄⣧ ⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⠀⠀⠀⠈⢿⣿⣿⣿⣿⣿⣆ ⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⢂⠻⣿⣿⣿⣿⣿⣄ ⠀⠀⠀⠀⠀⣿⣿⣿⣿⣹⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⠀⠀⠀⠀⠀⡄⠈⢿⣿⣿⣿⣿⣆ ⠀⠀⠀⠀⣿⣿⣿⣿⠁⡇⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠐⠸⠀⠀⠻⣿⣿⣿⣆⢦ ⠀⠀⢠⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡏⣧⠀⠀⠀⠀⠐⣇⠀⠀⠙⣿⣿⣿⡄⠙⣄ ⠀⣴⣿⣿⣿⣿⠏⠀⢸⠀⠀⠀⠀⠀⠀⡿⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣃⣈⣦⠀⠀⠀⠀⢹⠀⠀⠀⠸⣿⣿⣿⠀⠀⠳⣀ ⠋⣸⣿⣿⣿⡟⠀⠀⠀⡆⠀⠀⠀⠀⠀⡏⠙⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠀⢠⠀⠀⠀⢧⠀⠀⠀⠀⡇⠀⠀⠀⠘⣿⣿⣷⠀⠀⠘ ⠀⣿⣿⣿⢩⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⣀⠀⢱⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠂⢀⣴⣶⣿⣿⡀⠀⠀⢻⠀⠀⠀⠀⠹⣿⣿⡄ ⢸⣿⣿⠃⠈⠀⠀⢸⠀⣿⣆⠀⠀⠀⠀⣿⣿⣿⠷⠘⡀⠀⠀⠀⠀⠀⠀⢠⢹⡀⠈⡿⠻⣿⣛⢿⣿⣷⡀⠈⠀⠀⠀⠀⠀⢻⣿⣿ ⣿⣿⣿⠀⠀⠀⠀⢸⠀⡇⣼⣄⠀⠀⠀⢻⣿⡄⠑⠑⣿⡀⠀⠀⠀⢀⠀⠂⠇⠀⠀⠖⠛⢿⣿⣿⣌⢿⣿⣿⡆⠀⠀⠀⠀⠀⣿⣿⡀ ⣿⣿⡇⠀⠀⠀⠀⢸⠀⣾⣿⣿⡷⠿⣷⣤⣿⣿⡄⠀⠀⠀⠑⠤⡀⠀⠃⠀⠀⠀⠀⣿⣶⣿⣿⣿⣿⣆⠙⣿⣧⠀⠀⠀⠀⠀⣿⣿⡇ ⣿⣿⠁⠀⠀⠀⠀⠘⣾⣿⣿⠁⣴⣿⣿⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠸⡏⠙⣿⠉⠻⣿⠀⠀⣿⠀⠀⠀⣄⠀⣿⢸⣷ ⣿⣿⡇⠀⠀⠀⠀⠀⣿⣿⠁⠀⣿⣿⠋⣿⠏⠙⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⢀⢻⠀⠀⢀⡟⢀⣿⣸⢃⠟ ⣿⣿⣿⠀⡄⠀⠀⠀⠘⠻⡄⠀⢹⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡘⠀⢀⣿⠃⣿⣿⡗⠁ ⣧⣿⣿⣧⢹⡀⠀⠀⠀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⣴⣿⣿⣾⣿⣿⣿ ⢿⠘⣿⣿⣿⣿⣤⠀⠢⡀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣵⣿⣿⣿⣿⣿⣿⣿⣿⣷ ⠀⠉⣿⣿⣿⡿⣿⠻⣷⣬⣓⣬⣄⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠉⠈⠈⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⠃⠼⢉⣿⣿⣿⣿⣿⣿⣿ ⠀⠀⣿⣿⣿⣷⠀⠀⠀⠘⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⡏⠀⠀⢸⠀⢻⢿⣿⣿⡏⣿ ⠀⢸⣿⣿⣿⣿⠀⠀⠀⠀⢻⣿⣿⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣾⣿⣿⣿⣿⠀⠀⠀⢸⠀⠀⢸⣿⣿⠘⡀ ⢦⡿⣿⣿⣿⢿⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣶⣶⣦⡄⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠘⡄⠀⠈⣿⣿⡄⠱ ⣴⠛⣾⣿⣿⢸⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⡄⠀⠀⠀⠀⠀⠀⠀⣯⠛⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⣇⠀⠀⣿⣿⣿ ⠿⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⠟⠰⡾⠃⠀⠀⠀⠀⠀⠀⠀⠙⡟⠀⢻⣿⣿⣿⣿⣿⡆⠀⠀⠀⠸⠀⠀⠸⣿⣿⣷ ⠆⢳⣿⣿⡇⠀⠀⠀⠀⠀⠀⣿⣿⣿⠛⠿⠿⢿⡟⠀⠀⠉⠦⣀⡤⢶⠀⠖⠲⠶⠊⠀⠀⠀⢻⡛⠛⠛⣿⣿⠀⠀⠀⠀⠃⠀⠀⢿⣿⣿ */