傳送門

文章目錄

• 題意：
• 思路：

題意：

定義$f(x)$表示$x$的十進制下數位和，現在給你$a$，讓你選一個區間$[l,r]$，滿足${\sum }_{i=l}^{r}f(i)\mathrm{m}\mathrm{o}\mathrm{d}a=0$。

$1\le a\le 1e18$

要求輸出的$l,r$滿足$1\le l\le r\le 10^{200}$

思路：

考慮這樣一個事情，對于$x$，我們找一個$10^k>x$，那么此時$f(10^k+x)?f(x)=1$。

有了這個之后，我們自然的想構造出來$a$個這樣的對，這樣模$a$就是$0$了。

取一個比$a$大的$10$的冪次$10^{19}$，所以就會想到構造這樣的區間$[a+1,10^{19}+a]$，轉換成前綴和的形式$[1,10^{19}+a]?[1,a]$，顯然這是不行的，雖然這樣保證了$[1,a],[10^{19}+1,10^{19}+a]$兩個區間對應數$f$做差為$1$，并且有$a$個這樣的數，但是忽略了$[a+1,10^{19}]$這段區間對答案的貢獻，那么既然去不掉這段區間，那么不妨將這段區間加入答案中，也就是我們上面說的$a$對這樣的數，假設多出來$k$，那么我們只需要添加$a?k$對即可，考慮這些多出來的怎么計算。

我們考慮求出來${\sum }_{i=1}^{10^{19}}f(i)\mathrm{m}\mathrm{o}\mathrm{d}a$，設其為$k$，換句話說，我們現在需要加上$a?k$個$1$就可以達到要求了。考慮將原本區間$[1,10^{19}]$不斷右移，比如右移一次$[2,10^{19}+1]$，不難發現，這個時候原本的$1$的貢獻變成了$1+10^{19}$的貢獻，增加了$1$，所以我們右移$a?k$次，得到區間$[a?k+1,10^{19}+a?k]$，答案就是這個區間啦。

取一個比較大的$10$的冪次，防止移動過程中超過這個冪次即可。

// Problem: C. Hack it! // Contest: Codeforces - Codeforces Round #268 (Div. 1) // URL: https://codeforces.com/problemset/problem/468/C // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,INF=0x3f3f3f3f; const double eps=1e-6;LL f[30][10*20],mod; int a[30];LL dp(int pos,LL sum,int flag) {if(pos==0) return sum%mod;if(f[pos][sum]!=-1&&flag) return f[pos][sum];int x=flag? 9:a[pos];LL ans=0;for(int i=0;i<=x;i++) (ans+=dp(pos-1,sum+i,flag||i<x))%=mod;if(flag) f[pos][sum]=ans;return ans; }LL solve() {// int tot=0;// while(x) a[++tot]=x%10,x/=10;// return dp(tot,0,0);for(int i=1;i<=19;i++) a[i]=0;a[20]=1;return dp(20,0,0); }inline __int128 read() {__int128 x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; }inline void write(__int128 x) {if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0'); }int main() { // ios::sync_with_stdio(false); // cin.tie(0);memset(f,-1,sizeof(f));scanf("%lld",&mod);LL k=solve()%mod;write((__int128)mod-k+1); putchar(' ');write((__int128)100000000000000000*100+mod-k);puts("");return 0; } /**/

總結

以上是生活随笔為你收集整理的Codeforces Round #268 (Div. 1) C. Hack it! 数位dp + 构造数位的全部內容，希望文章能夠幫你解決所遇到的問題。

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