P8022 [ONTAK2015] Cięcie 題解

題目傳送門

題目大意

給出一個長為 k k k 的數字串以及三個質數 p p p , q q q , r r r ,要求将數字串分成三段 A A A， B B B， C C C ，使 A A A， B B B， C C C 都不含前導 0 0 0 且 p ∣ A p|A p∣A ， q ∣ B q|B q∣B ， r ∣ C r|C r∣C 。

題目分析

很容易想到先枚舉出所有滿足條件的 A A A， B B B 的分界線後，對每條分界線右端的剩餘部分繼續枚舉所有滿足條件的 B B B， C C C 的分界線。但是由于 1 ≤ k ≤ 1 0 6 1\le k\le10^6 1≤k≤106，是以該做法可能會 TLE，于是我們嘗試優化該做法。

首先從前往後枚舉 A A A 和 B B B 的分界線，設分界線右端的剩餘部分為 R R R ，那麼可以用 s u m [ i ] sum[i] sum[i] 記錄下滿足 A ≡ 0 ( m o d p ) A≡0\pmod p A≡0(modp) 且 R ≡ i ( m o d q ) R≡i\pmod q R≡i(modq) 的個數。然後從後往前枚舉 B B B 和 C C C 的分界線，對于每個位置，首先删除 R R R 與 C C C 重合的部分，設剩餘的部分為 L L L，将 L ≡ C ( m o d q ) L≡C\pmod q L≡C(modq) 的個數，即 s u m [ C   m o d   q ] sum[C\bmod q] sum[Cmodq] 統計入答案中。時間複雜度為 O ( n ) O(n) O(n) 。

此外還需注意題目中條件每一段都不含前導 0 0 0，對于細節進行單獨處理即可。

（這道題細節真的很多，有耐心去做才能做對）

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,p,q,r,a[1000010],tot1,tot2,A[1000010],C[1000010],modq,modr,sum[100010];
ll ans;
char ch[1000010];
int main(){
	int i;
	scanf("%d%d%d%d",&n,&p,&q,&r);
	cin>>ch;
	for(i=1;i<=n;i++)a[i]=ch[i-1]-'0';
	for(i=1;i<=n;i++)A[i]=(A[i-1]*10+a[i])%p;
	tot1=1;
	for(i=n;i>=1;i--){
		C[i]=(C[i+1]+a[i]*tot1)%q;
		tot1=(tot1*10)%q;
	}
	for(i=1;i<n;i++){
		if((a[1]==0&&i!=1)||a[i+1]==0)continue;
		if(A[i]==0)sum[C[i+1]]++; 
	}
	tot1=1;tot2=1;
	for(i=n;i>=3;i--){
		modq=(modq+a[i]*tot1)%q;
        modr=(modr+a[i]*tot2)%r;
        if(a[i]!=0&&A[i-1]==0)sum[C[i]]--;
        if((a[i]!=0||i==n)&&modr==0)ans+=(ll)sum[modq];
        if(modr==0&&a[i-1]==0&&A[i-2]==0&&(a[1]!=0||i==2)&&(a[i]!=0||i==n))ans++;
		tot1=(tot1*10)%q;
		tot2=(tot2*10)%r;
	}
	printf("%lld",ans);
	return 0;
}