51Nod 算法马拉松7 B选数字 - dblank

51Nod 算法马拉松7 B选数字

System Message (命题人)
基准时间限制:1 秒 空间限制:131072 KB 分值: 80
当给定一个序列a[0],a[1],a[2],...,a[n-1] 和一个整数K时,我们想找出,有多少子序列满足这么一个条件:把当前子序列里面的所有元素乘起来恰好等于K。

样例解释:

对于第一个数据,我们可以选择[3]或者[1(第一个1), 3]或者[1(第二个1), 3]或者[1,1,3]。所以答案是4。
Input
多组测试数据。在输入文件的第一行有一个整数T(0< T <= 20),表示有T组数据。
接下来的2*T行,会给出每一组数据
每一组数据占两行,第一行包含两个整数n, K(1<=n<=1000,2<=K<=100000000)他们的含意已经在上面提到。
第二行包含a[0],a[1],a[2],...,a[n-1] (1<= a[i]<=K) 以一个空格分开。
所有输入均为整数。
Output
对于每一个数据,将答案对1000000007取余之后输出即可。
dp[i][j]表示选到第i个数字,乘积为k的第j个因子的选法,dp[i][j] =sum(dp[1~(i-1)[v[j]/num[i]]), 其中v是k的因子数组,三重循环会超时,用树状数组优化求和部分。
#include<iostream>  
#include<algorithm>  
#include<cstring>  
#include<cstdio>  
#include<queue>  
#include<vector>  
#include<map>  
#include<cmath>  
using namespace std;  
int num[1010], n, k, dp[1010][1010];  
const int M = 1000000007;  
vector<int>v;  
map<int, int>mp;  
int lowbit(int x)  
{  
    return x&(-x);  
}  
int update(int x,int y, int va)  
{  
    while(x<=n)  
    {  
        dp[x][y] = (dp[x][y] + va)%M;  
        x += lowbit(x);  
    }  
}  
int getsum(int x, int y)  
{  
    int sum = 0;  
    while(x>=1)  
    {  
        sum = (sum + dp[x][y])%M;  
        x -= lowbit(x);  
    }  
    return sum;  
}  
int main()  
{  
    int t;  
    cin>>t;  
    while(t--)  
    {  
        scanf("%d%d", &n, &k);  
        for(int i = 1; i<=n; i++)  
            scanf("%d", &num[i]);  
        int s = sqrt(k);  
        v.clear();  
        mp.clear();  
        for(int i = 1; i<=s; i++)  
        {  
            if(k % i == 0)  
            {  
                v.push_back(i);  
                v.push_back(k/i);  
            }  
        }  
        sort(v.begin(), v.end());  
        for(int i = 0; i<v.size(); i++)  
            mp[v[i]] = i + 1;  
        memset(dp, 0, sizeof(dp));  
        s = v.size();  
        for(int i = 1; i<=n; i++)  
        {  
            if(mp[num[i]])  
                update(i, mp[num[i]], 1);  
            for(int j = 0; j<s; j++)  
            {  
                if(v[j] % num[i] == 0)  
                {  
                    int id = mp[v[j]/num[i]];  
                    int sum = getsum(i-1, id);  
                    update(i,j+1, sum);  
                }  
            }  
        }  
        /* for(int i = 1; i<=n; i++) 
        { 
             for(int j = 1; j<=s; j++) 
                 printf("%d ", dp[i][j]); 
             printf("\n"); 
         }*/  
        int ans = 0;  
        printf("%d\n", getsum(n, s));  
    }  
    return 0;  
}

 

相关文章

发表新评论