2019 Multi-University Training Contest 6 11 Dimensions DP

1706 단어 생각dp
This way

제목:


너에게 불완전한 수를 주겠다. n자리가 있고 m의 배수라는 것을 알고, 모두 q개의 질문을 할 것이다. 매번 너에게 그것의 k가 얼마나 큰지 물어볼 때마다.

문제 풀이:


dp[i][j]는 i위까지 모드m이 j일 때의 개수를 나타낸다.우리는res로 현재 매거된 모듈 m이 얼마인지 표시한 다음에 앞 모듈 m의 여수를 매거하면 상태 이동 방정식은 dp[i][(re s + k)% m] + = dp [i-3] [k]이다.dp[i][(res+k)\%m]+=dp[i-1][k]; dp[i][(res+k)%m]+=dp[i−1][k]; 그것은 폭발할 것이니 주의해라. 그러면 우리는 그가 k에 미치지 못하는 값에 도달하도록 해야 한다.그리고 우리는 다음 20위를 열거했다. 왜냐하면 1 0 18 ∗ 20 < 1 0 20 10^ {18} * 20 < 10 {20} 1018 ∗ 20< 120 은 현재 1위에 대해 우리는 그 다음 순위를 살펴보았기 때문이다. 왜냐하면 이 모델을 추출한 후에 나는 그것이 어디에서 옮겨왔는지 모르겠지만 이 순위의 값을 확정했다. 그러면 나는 다음 순위가 어디에서 옮겨왔는지 알 수 있다.
#include
using namespace std;
#define ll long long
const int N=5e4+5;
const ll mod=1e9+7;
const ll inf=2e18;
char s[N];
int a[N];
ll p_mod[N],p_m[N],dp[N][21];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,q;
        scanf("%d%d%d",&n,&m,&q);
        scanf("%s",s);
        ll ans=0,_m=0;
        int cnt=0;
        for(int i=0;iinf&&(dp[i][(res+k)%m]=inf);
                }
            }
        }
        _m=(m-_m)%m;
        ll aa=ans;
        while(q--)
        {
            ll k;
            scanf("%lld",&k);
            if(dp[cnt][_m]

좋은 웹페이지 즐겨찾기