與巨

• description
• solution
• code

description

【題目描述】
定義無窮序列$f:f_1=1,f_n=f_{n?1}?2+1$

定義函數$G(x)={\min }_{f_i\ge x}(f_i)$

定義$d{p}_{c,0}=0,d{p}_{c,i}=\max (d{p}_{c,i?1},[((i?c)\&G(i))=i]?i)$

求${\sum }_{i=0}^{n}d{p}_{c,i}(\mathrm{m}\mathrm{o}\mathrm{d}998244353)$

【輸入格式】
第一行輸入一個整數T，表示測試用例的組數。
每組測試用例輸入一行包含兩個整數n, c。
其中𝐧以二進制形式表示，且𝐧不含有前導 0。
【輸出格式】
對于每組測試用例輸出一行一個整數表示答案。
【樣例 1 輸入】

5 1001 1 11111 1 101010111101 8999 10100101111010101 799 10010010 233

【樣例 1 輸出】

45 496 2835797 707482963 9940

【數據范圍】

$1\le T\le 10;1\le |n|\le 10^7,1\le c\le 10^{18},{\sum }_{i=1}^T|n|\le 10^7$

solution

觀察到$f_i$的生成遞推式，最后結果一定形如000..00011...111

設$G(i)=2^{t+1}?1$，$G(i)$必然是這種形式，$t$為二進制最高位

則$x\&G(i)$相當于$x\text{mod}{2}^{t+1}$

則，有$(i?c)\&G(i)=i?(i?c)\text{mod}{2}^{t+1}=i?i?(c?1)\text{mod}{2}^{t+1}=0$

以$2^p?q=c?1$來重新表示，則$i$必須含有因子$2^{t+1?p}$

設$m=|n|$，可以枚舉$t$

• $t<m?1$

  則$[2^t,2^{t+1}?1]$內的所有數都在$n$之內，其最高位均為$t$

  設$g=t+1?p$，那么$i$含有因子$2^g$意味著$i$的低$g$位全為$0$

  這樣的數為$2^t,2^t+2^g,...,2^t+x?2^g$ 【$2^t+(x+1)2^g=2^{t+1}$】

  這是一個$x+1$項的等差數列，利用公式容易求得

  同時每個數都會對最終答案貢獻$2^g$次【對于$G(i)=2^a$，那么$G(i+k,k\in [1,2^a])=2^{a+1}$，$2^{a+1}$都會貢獻，一共是$2^a$】

• $t=m?1$，由于$2^{t+1}>n$，但需要滿足$2^t+x?2^t\le n?x=?\frac{n}{2^g}??2^{t?g}$

  對這個$x+1$項的等差數列同樣方法計算貢獻后，最后一項被計算了$2^g$次，計數范圍為$[2^t+x?2^g,2^t+(x+1)?2^g?1]$

  此時多計數了$2^t+(x+1)?2^g?1?n$次，減去多的貢獻即可

code

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define int long long #define mod 998244353 #define maxn 10000005 int mi[maxn]; char s[maxn]; const int inv2 = ( mod + 1 ) >> 1;int calc( int a, int d, int n ) {return ( a * n % mod + n * ( n - 1 ) % mod * d % mod * inv2 % mod ) % mod; }signed main() {freopen( "and.in", "r", stdin );freopen( "and.out", "w", stdout );mi[0] = 1;for( int i = 1;i < maxn;i ++ ) mi[i] = ( mi[i - 1] << 1 ) % mod;int T, n, c;scanf( "%lld", &T );while( T -- ) {scanf( "%s %lld", s + 1, &c );n = strlen( s + 1 );c --;int ans = 0;if( ! c ) {for( int i = 1;i <= n;i ++ )ans = ( ( ans << 1 ) + ( s[i] ^ 48 ) ) % mod;printf( "%lld\n", ans * ( ans + 1 ) % mod * inv2 % mod );}else {if( c & 1 ) { printf( "0\n" ); continue; }else {int p = 0;while( ! ( c & 1 ) ) c >>= 1, p ++;for( int t = 0;t < n;t ++ ) {int g = max( 0ll, t + 1 - p );if( t < n - 1 )ans = ( ans + mi[g] * calc( mi[t], mi[g], mi[t + 1 - g] - mi[t - g] ) ) % mod;else {int k = 0;for( int i = 1;i <= n - g;i ++ ) k = ( ( k << 1 ) + ( s[i] ^ 48 ) ) % mod;//n/2^g下取整 int x = ( k - mi[t - g] ) % mod; ans = ( ans + mi[g] * calc( mi[t], mi[g], x + 1 ) ) % mod;//x=k-2^{t-g}=k-mi[t-g] x+1項 int lst = ( mi[t] + x * mi[g] ) % mod;//計算末項 2^t+x*2^gint l = 0;int r = ( lst + mi[g] - 1 ) % mod;//末項的下一項 2^t+(x+1)*2^g 還有一個-1 for( int i = 1;i <= n;i ++ ) l = ( ( l << 1 ) + ( s[i] ^ 48 ) ) % mod; //-n ans = ( ans - ( r - l ) * lst ) % mod;}}}printf( "%lld\n", ( ans + mod ) % mod );}}return 0; }

總結

以上是生活随笔為你收集整理的牛客ＮＯＩＰ２０２１提高组ＯＩ赛前模拟赛第一场Ｔ３——与巨（数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。