結果
問題 | No.315 世界のなんとか3.5 |
ユーザー |
|
提出日時 | 2016-06-27 15:17:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 227 ms / 2,000 ms |
コード長 | 2,728 bytes |
コンパイル時間 | 1,633 ms |
コンパイル使用メモリ | 171,460 KB |
実行使用メモリ | 57,984 KB |
最終ジャッジ日時 | 2024-10-11 22:23:58 |
合計ジャッジ時間 | 5,930 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<ll> vll;const int MOD=(int)1e9+7;void add(int &x, int y){x+=y;if(x>=MOD)x-=MOD;}const int MAX = (int)2e5 + 1;int dp1[MAX][2][2][2][3], dp2[10][2][2][2][3][25][32];char SA_[MAX], SB_[MAX];string A, B;int P, LEN, pow5, pow2;int f(int pos, int greaterThanA, int lessThanB, int use3, int m3, int m25, int m32){if(LEN - pos < 6){int cur = pos - LEN + 5;int &res = dp2[cur][greaterThanA][lessThanB][use3][m3][m25][m32];if(res != -1)return res;if(pos == LEN){if(m3 != 0 && use3 == 0)return res=0;else if(m25%pow5==0 && m32%pow2==0) return res=0;else return res = 1;}res = 0;rep(digit, 10){if(greaterThanA == 0 && digit < A[pos])continue;if(lessThanB == 0 && digit > B[pos])continue;int n3 = (m3 * 10 + digit) % 3;int n25 = (m25 * 10 + digit) % 25;int n32 = (m32 * 10 + digit) % 32;add(res,f(pos + 1, greaterThanA | (digit>A[pos]), lessThanB | (digit < B[pos]), use3 | (digit == 3), n3, n25, n32));}return res;} else{int & res = dp1[pos][greaterThanA][lessThanB][use3][m3];if(res != -1)return res;res = 0;rep(digit, 10){if(greaterThanA == 0 && digit < A[pos])continue;if(lessThanB == 0 && digit > B[pos])continue;int n3 = (m3 * 10 + digit) % 3;add(res,f(pos + 1, greaterThanA | (digit>A[pos]), lessThanB | (digit < B[pos]), use3 | (digit == 3), n3, 0, 0));}return res;}}int main(){while(~scanf("%s%s%d", SA_, SB_, &P)){A = string(SA_);B = string(SB_);int dif = sz(B) - sz(A);if(dif)A = string(dif, '0') + A;each(c, A)c -= '0';each(c, B)c -= '0';LEN = sz(A);MEM(dp1, -1);MEM(dp2, -1);for(int i = 25; i; i /= 5)if(P%i == 0){pow5 = i;break;}for(int i = 32; i; i /= 2)if(P%i == 0){pow2 = i;break;}int ans = f(0, 0, 0, 0, 0, 0, 0);cout << ans << endl;}}